LeetCode-518.零钱兑换II

╰+攻爆jí腚メ 2024-03-25 16:46 57阅读 0赞

#### 目录 ####

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

题目来源  
[518.零钱兑换II][518._II]

### 题目分析 ###

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

### 回溯法 ###

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;i<coins.length;i++){
        
                sum+=coins[i];
                backtracking(coins,i,sum,amount);
                sum-=coins[i];
            }
        }
    }

![在这里插入图片描述][f146175203d246ada34618de6ff7cc6d.png]

### 动态规划 ###

这道题和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];
        }
      
    }

![在这里插入图片描述][e9d2cc47bc5e4f27920c4f184a112a81.png]  
![在这里插入图片描述][6235665a7ad945398acc8609e04c5324.png]

### 动态规划(压缩) ###

*  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数组

![在这里插入图片描述][c2653d576af34b9385e121ac238fe680.png]

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;i<coins.length;i++){
        
                for(int j = coins[i];j<=amount;j++){
        
                    dp[j] = dp[j] + dp[j-coins[i]];
                }
            }
            return dp[amount];
        }
      
    }

![在这里插入图片描述][d69ce3affe9c4af685c60e89a7534ba8.png]

[518._II]: https://leetcode.cn/problems/coin-change-ii/
[e65fc8ddc1e749258ea28aa74b20e351.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/b3aa7d707b45480fa7060a4721349482.png
[f146175203d246ada34618de6ff7cc6d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/6df2de1513074eed87924de008c91395.png
[e9d2cc47bc5e4f27920c4f184a112a81.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/75e265482abc4edf821b7a5d8a0d8a52.png
[6235665a7ad945398acc8609e04c5324.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/9c7ffab6d1ca41f58802c988cfa1836e.png
[c2653d576af34b9385e121ac238fe680.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/71c29fa09c14434188baec33a9263a01.png
[d69ce3affe9c4af685c60e89a7534ba8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/b74e2ccfa2be40a3ab7a94a307a7ed1e.png