动态规划-硬币

Question

考虑下面的伪代码，其中d是面额值的数组，k是面额的数目，n是要进行更改的数量。

Change(d; k; n)
1 C[0]  <- 0
2 for p <-  1 to n
3     min  <- INFINITE
4     for i  <- 1 to k
5         if d[i] <= p then
6           if 1 + C[p - d[i]] < min then
7               min  <- 1 + C[p - d[i]]
8               coin  <- i
9     C[p] <-  min
10    S[p] <-  coin
11 return C and S

我读过很多关于这个具体问题的信息，但是我还是不明白为什么：1 + C[p-d[i]] ->我真的不明白这个部分，你为什么要用它，谁能给我解释一下吗？

Answer 1

为了回答你的问题，你需要了解每个变量代表什么，以及算法在做什么。

算法到达解决方案的过程试图计算从1到n (包括在内)对所有金额进行更改所需的硬币数量。这就是外部循环的目的:它通过1通过n迭代当前的“目标”，让循环体为该目标提供答案。

本质上，算法是这样的：

• 我知道，如果是零，我需要零钱来兑换。
• 看看我需要多少硬币才能给1找零
• 知道我需要为1兑换多少硬币，看看我需要为2兑换多少硬币
• 知道需要通过2为2兑换多少硬币，看看需要为3兑换多少硬币
• 知道需要通过4为4兑换多少硬币，看看需要为4兑换多少硬币
• ..。
• 知道需要通过n-1为n-1兑换多少硬币，看看需要为n兑换多少硬币

p的值表示当前的目标--即我们试图对其进行更改的金额。数组C表示到目前为止我们为从1到p-1的所有金额找到的解决方案，包括。

对于每个金额，该算法尝试使用每个面额d[i]中的硬币来寻找解决方案。

现在，您已经准备好理解1 + C[p-d[i]]的含义了:我们正试图对p进行更改，因此C[p-d[i]]是为p-d[i]做出更改所需的最小数量的硬币。因此，公式说：“如果我知道要用x硬币来改变p-d[i]，并且我有一个d[i]面额的硬币，那么我可以通过添加一个d[i]硬币(因此，表达式的1 + ...部分)到达p。