algorithm - 该算法是否涵盖了寻找总和的最小硬币变化的所有情况？

Question

我正在尝试解决最小硬币找零问题。问题是:给定一个值 V，如果我们想找零 V 分，并且我们有无限供应的每个 C = { C1, C2, .. , Cm} 值的硬币，进行找零的最小硬币数量是多少？

我建议的算法是:

以数组 arr[1..V] 开始，其中 V 是值:

1. 对于所有面额，初始化 arr[d]=1，因为这是基本情况。如果值(value)==一枚硬币的妖魔化，则只需要1枚硬币，因此是最少的

2. 对于 i : 1...V 中的所有值: 计算为“i”值进行找零所需的最少硬币数量。2.1.这可以通过以下方式完成: 对于所有 j: 1....(i-1) arr[i]=min(arr[i],arr[j]+arr[i-j]);

3. 返回arr[V];

这个逻辑是有缺陷的还是涵盖了所有情况？大多数 DP 解决方案都使用二维数组，我不明白为什么他们会使用 O(n^2) 内存空间，如果它存在并且是正确的。谢谢你。

Answer 1

无法获取某些值 V 的情况如何？

即我们有硬币 {5,6,7,8,9}，但我们不能将值设为 1,2,3,4，您应该将所有值 != demoniation cells 初始化为无穷大常数或类似值。

现在由于大多数人使用 O(n^2) 内存的原因:

这个问题有多种形式，最常见的一种是每个硬币只能使用一次，在这种情况下使用状态 dp[i][j] - 在考虑第 i 个硬币后总和为 j 的最小硬币似乎更容易对于大多数人来说理解，即使这也可以用 O(n) 内存完成(只是向后循环)