动态规划 Coin Change Limited Coins

Question

动态规划变化问题（有限硬币）。我正在尝试创建一个作为INPUT的程序：

int coinValues[]; //e.g [coin1,coin2,coin3]
int coinLimit[]; //e.g [2 coin1 available,1 coin2 available,...]
int amount; //the amount we want change for.

输出：

int DynProg[]; //of size amount+1.

并且输出应该是一个大小为amount+1的数组，其中每个单元格代表我们需要为单元格索引的数量提供更改的最佳硬币数量。

示例：假设我们在索引：5 处有 Array 的单元格，内容为 2。这意味着，为了改变 5（INDEX）的数量，您需要 2（单元格的内容）硬币（最佳解决方案） .

基本上我需要这个视频的第一个数组(C[p]) 的输出。这是完全相同的问题与大差异的有限公司硬币。 链接到视频。

注意：看视频理解，忽略视频的第二个数组，记住我不需要组合，而是DP数组，这样我就可以找到哪些硬币作为找零。

谢谢你。

Answer 1

考虑下一个伪代码：

for every coin nominal v = coinValues[i]:
    loop coinLimit[i] times:
        starting with k=0 entry, check for non-zero C[k]:
            if C[k]+1 < C[k+v] then
                  replace C[k+v] with C[k]+1 and set S[k+v]=v

清楚吗？