对于硬币变化问题（动态规划方法），递归关系中+1的含义是什么？

Question

我看到了硬币变化问题。通常，输入为n（要返回的更改）和可用的面额（以美分为单位的硬币值），v1 <v2 <v1 <... <vk;目标是用最小数量的硬币进行n美分的更改。

我正在读哥伦比亚大学的this pdf，但我不明白为什么，在第6张幻灯片中，我们在递归关系中得到+1：

它代表我们已经使用过的硬币吗？

Answer 1

假设我的面额看起来像这样：d = [1, 5, 10, 25]。让我们假设n，要返回的更改是26.这意味着：

C[26] = min{C[26 - d[i]] + 1}

可以表示为：

C[26] = min{C[25], C[21], C[16], C[1]} + 1。

这里的“+1”只是你需要添加到一个先前解决的子问题（例如C [25]，C [21]）以得到C [26]的硬币。

如果我们考虑一个更简单的例子，比如n = 6，具有相同的面额，我们知道重现将是：

C[6] = min{C[6 - d[i]]} + 1

要么：

C[6] = min{C[5], C[1]} + 1

我们知道C [5]是1（因为混合中5的面值为5美分的最小方法是1）并且类似地C [1] = 1.这里的最小值只有1，所以1 + 1 = 2和6美分所需的最小硬币数量是2个硬币。

Answer 2

C[p]表示您从可用硬币阵列d建立面额p的最小硬币数量。

因此，要创建这样的总和，你必须选择硬币d[i]，使d[i]<p。

我们假设您从d中选择了硬币d [i]。这意味着你现在的硬币计数是一个。

现在为了得到总和p，收集更多的硬币为p-d[i]总和。

但是你已经在p-d[i]中制作了总和C[p-d[i]]所需的min_coins。

这意味着制作和p的一个可能的硬币计数是1+C[p-d[i]]。

但是d[i]<p有可能存在多种面额，那么你必须选择最小的结果，这正是你的功能所做的。

通过这种方式你可以理解+1作为我们正在考虑制作总和p的第一枚硬币。