题解 | #兑换零钱(一)#

比如

1,2,5

举例

1、比如要凑11元，金额加+1，凑不到金额则是-1，定义长度为12的数组，这个比较简单，比如dp[0]==0,dp[11]则为凑11元的数量

int[] dp =[-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1]

默认凑不到

2、首次遍历(为方便理解，单独遍历一次塞进去，注意边界值和数值)

凑1元，需要1张，dp[1]=1

凑2元，需要1张，dp[2]=1

凑5元，需要1张，dp[5]=1

dp =[-1,1,1,-1,-1,1,-1,-1,-1,-1,-1,-1]

3、

dp[3]，遍历，凑3元

dp[3]=dp[2]+1 or dp[1]+1

这里需要理解一下

dp[3]=dp[3-1]+1 = 2 or dp[3-2]+1

3元-1元=2元，也就是用1张2元+1元(1张)

3元-2元=1元，也就是用1张1元+2元(1张)

这里也有前提，如果dp[2]为-1怎么算

dp[3] 默认值为-1

dp[3-1]+1 = 2

dp[3-2]+1 = 2

最终dp[3]=2

dp[4] = dp[4-1]+1（3） or dp[4-2]+1 (2)

最终dp[4]=2