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

Question

一直在尝试了解如何在此页面上使用动态编程

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

给定 N 个硬币的列表，它们的值（V1、V2、...、VN）和总和 S.找到最小数量的硬币，其总和为 S（我们可以根据需要使用任意数量的一种类型的硬币），或者报告不可能以它们总和为 S 的方式选择硬币。

给定价值为 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]

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

更令人困惑的是，当总和为 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]