python - 在动态编程硬币示例中使用无穷大 - 为什么这不会失败？

Question

一直在努力了解如何在此页面上使用动态规划

https://www.topcoder.com/community/data-science/data-science-tutorials/dynamic-programming-from-novice-to-advanced/

给定 N 个硬币的列表，它们的值 (V1, V2, … , VN) 和总和 S。找到总和为 S 的最小硬币数量(我们可以使用一种类型的硬币如我们所愿)，或者报告不可能以总和为 S 的方式选择代币。

给定值(value) 1、3 和 5 的硬币。总和 S 设为 11。

Set Min[i] equal to Infinity for all of i
Min[0]=0

For i = 1 to S
For j = 0 to N - 1
   If (Vj<=i AND Min[i-Vj]+1<Min[i])
Then Min[i]=Min[i-Vj]+1

Output Min[S]

我很困惑为什么我们要为所有 i 设置无穷大。

更令人困惑的是当总和为 1 时

If (Vj<=i AND Min[i-Vj]+1<Min[i]) 

Min[1] 不会是未定义的吗？代码不会在这里失败吗？他们为什么要添加 +1？？

或者它会继续下去，因为它是无限的吗？他们为什么在这里使用无限？什么是 N-1 他们从哪里得到的？

总的来说，我发现他们的解释很难理解。

Answer 1

希望这是直接翻译:

def dp_coin(S, coins):
    # set all values to infinity in range S/sum needed
    mn = [float("inf") for j in range(S+1)]
    # takes 0 coins to sum 0
    mn[0] = 0
    # start at second index 1
    for i in range(1, S+1):
        for j in range(len(coins)):
            if coins[j] <= i and mn[i-coins[j]]+1 < mn[i]:
                mn[i] = mn[i-coins[j]] + 1
    return mn[-1]

print(dp_coin(11, [1, 3, 5]))
3

如果你打印 mn 你会看到:

[0, 1, 2, 1, 2, 1, 2, 3, 2, 3, 2, 3]

与表格相同:

Sum Min. nr. of coins   Coin value added to a smaller sum to
obtain this sum (it is displayed in brackets)
0   0   -
1   1   1 (0)
2   2   1 (1)
3   1   3 (0)
4   2   1 (3)
5   1   5 (0)
6   2   3 (3)
7   3   1 (6)
8   2   3 (5)
9   3   1 (8)
10  2   5 (5)
11  3   1 (10)

S指的是需要的总金额，coins[j]相当于Vj，N是指硬币。

可以删除内部循环并简单地遍历硬币:

def dp_coin(S, coins):
    mn = [float("inf") for j in range(S+1)]
    mn[0] = 0
    for i in range(1, S+1):
        for j in coins:
            if j <= i and mn[i-j]+1 < mn[i]:
                mn[i] = mn[i-j] + 1
    return mn[-1]