518. 零钱兑换 II

思路

该题目是一个组合问题。

动规五部曲

1.定义dp数组

dp数组：dp[i]为当前amount=i时，一共有dp[i]种方法。

2.递推公式

因为该题为组合问题，所以dp[j]+=dp[j-coins[i]]。

当i为5的时候

• 已经有一个1（coins[i]） 的话，有 dp[4]种方法 凑成 dp[5]。
• 已经有一个2（coins[i]） 的话，有 dp[3]种方法 凑成 dp[5]。
• 已经有一个3（coins[i]） 的话，有 dp[2]中方法 凑成 dp[5]
• 已经有一个4（coins[i]） 的话，有 dp[1]中方法 凑成 dp[5]
• 已经有一个5 （coins[i]）的话，有 dp[0]中方法 凑成 dp[5]

那么凑整dp[5]有多少方法呢，也就是把 所有的 dp[j - coins[i]] 累加起来。

3.dp数组初始化

根据dp数组的含义可以知道dp[0]=1;

4.遍历顺序

根据递推公式可以知道要正序遍历。但是因为该物品可以重复放入，所以内层也是正序遍历。

5.打印dp数组

dp数组最后一个元素就是结果。

代码

class Solution {    public int change(int amount, int[] coins) { int dp[] = new int[amount+1]; int l = coins.length; dp[0]=1; for(int i =0;i<l;i++){     for(int j = coins[i];j<=amount;j++){  dp[j]+=dp[j-coins[i]];     } } return dp[amount];    }}