在动态规划硬币中使用无限的例子，为什么这不会失败？

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时

^{pr2}$

Min[1]不是未定义的吗？代码不会在这里失效吗？为什么他们要加+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，您将看到：

^{pr2}$

与表格相同：

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是指硬币。在

内环可以移除，只需在硬币上重复：

^{4}$