algorithm - 动态规划 - 硬币

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找零多少硬币>
• 知道从 1 到 2 我需要找零多少硬币，看看 3 我需要找多少硬币>/li>
• 知道从 1 到 4 我需要找零多少硬币，看看 4 我需要找多少硬币>/li>
• ...
• 知道从 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] 硬币来达到 p(因此，1 + ... 表达式的一部分)。