动态规划--找钱问题

问题：

设有n种不同面值的硬币，各硬币的面值存于数组T[1:n]中。现要用这些硬币来找钱。可以使用的各种面值的硬币个数不限。

当只用硬币面值T[1]，T[2]，……T[i]时，可以找出钱数j的最少硬币个数记为

C(i,j).若只用这些硬币面值，找不出钱时，记C(i,j)=∞。给出C(i,j)的递归表达式及其初始条件。1<=i<=n,1<=j<=L.

 

解决：

递归式子：用c[i][j]存储最后结果；

c[i][j] = min(c[i-1][j], c[i][j-t[i]]+1) (j>=t[i])

c[i][j] = c[i-1][j] (j

初始条件：

c[1][j] = j%t[1] (j%t[1] == 0)

c[1][j] = ∞ (j%t[1] != 0)