目录

• • 题目分析
  • 回溯法
  • 动态规划
  • 动态规划(压缩)

题目来源
518.零钱兑换II

题目分析

1.转换成背包问题，由于每一种面额的金币可以选择多次，所以是完全背包问题。
2.题目要求我们求组合，而不是排列

回溯法

class Solution {int ans;public int change(int amount, int[] coins) {if(coins.length == 0){return 0;}backtracking(coins,0,0,amount);return ans;}private void backtracking(int[] coins,int startIndex,int sum,int amount){if(sum == amount){ans++;return;}if(sum>amount){return;}for(int i =startIndex;isum+=coins[i];backtracking(coins,i,sum,amount);sum-=coins[i];}}
}

动态规划

这道题和0-1背包的问题不一样了，是可以多选(看下面的图就懂了)
dp[i][j - coins[i - 1]]而不是0-1背包之前的 dp[i-1][j - coins[i - 1]]
还有要多留一行，在0-1背包直接是nums[0]就开始了

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

动态规划(压缩)

• 1.确定dp数组以及下标的含义

dp[j]：凑成总金额j的货币组合数为dp[j]

• 2.确定递推公式

dp[j] 就是所有的dp[j - coins[i]]（考虑coins[i]的情况）相加。
所以递推公式：dp[j] += dp[j - coins[i]];也可以理解为dp[j] = dp[j]+dp[j - coins[i]];

• 3.dp数组如何初始化

首先dp[0]一定要为1，dp[0] = 1是 递归公式的基础。如果dp[0] = 0 的话，后面所有推导出来的值都是0了。
如果正好选了coins[i]后，也就是j-coins[i] == 0的情况表示这个硬币刚好能选，此时dp[0]为1表示只选coins[i]存在这样的一种选法。

• 4.确定遍历顺序

因为是组合
外层for循环遍历物品（钱币），内层for遍历背包（金钱总额）

• 5.举例推导dp数组

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