力扣爆刷第128天之动态规划五连刷（一个零、零钱兑换、组合）

终结背包问题：这篇文章和上一篇。

动态规划解题步骤：

1. 确定dp数组（dp table）以及下标的含义。
2. 确定递推公式。
3. dp数组如何初始化。
4. 确定遍历顺序。
5. 举例推导dp数组。

背包问题总结

背包问题：一维数组，dp[j] = Math.max(dp[j], dp[j-nums[i]] + nums[i])。

01背包遍历顺序： 先物品后背包，物品正序，背包逆序。

如若背包正序则会出现同一个物品重复放入，如物品1重量为1，背包空间为1时放入了，背包空间为2时又放入了。
如果先背包后物品，为了避免重复放入背包依然是逆序，背包容量固定时，每种背包容量只能放入一个物品，即为最大的物品，小的物品都放不进来或者被覆盖了。

求组合数排列数：dp[j] += dp[j - nums[i]]

完全背包遍历顺序： 物品背包没有先后顺序，物品背包都是正序。因为同一个物品不限量可以放入多次，在背包采用正序中。

完全背包求组合数，物品在外，背包在内。求排列数，背包在外，物品在内。

一、474. 一和零

题目链接：https://leetcode.cn/problems/ones-and-zeroes/description/
思路：一和零是双重背包，本质上还是0 1 背包，只不过现在背包的容量有两个指标，所以还是0 1背包的套路，定义dp[i][j]数组表示容量为i个0和j个1的背包最多可以装下的字符串数量，故当前背包装物品的数量依赖于上一个容量较小时装的数量，具体是多少容量呢，当然是可以满足装下最大数量的容量，那到底是什么呢，就是例如有一个字符串有2个0和3个1，依赖于dp数组的定义，想让当前空间利用率最大，自然是把空间都占满，dp[i][j] = dp[i-2][j-3] + 1。故递推公式为dp[i][j] = Math.max(dp[i][j], dp[i-nums[0]][j-nums[1]] + 1);

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int[][] dp = new int[m+1][n+1];
        for(String s : strs) {
            int[] nums = countNums(s);
            for(int i = m; i >= nums[0]; i--) {
                for(int j = n; j >= nums[1]; j--) {
                    dp[i][j] = Math.max(dp[i][j], dp[i-nums[0]][j-nums[1]] + 1);
                }
            }
        }
        return dp[m][n];
    }

    int[] countNums(String s) {
        int[] nums = new int[2];
        int a = 0, b = 0;
        for(int i = 0; i < s.length(); i++) {
            if(s.charAt(i) == '0') {
                a++;
            }else{
                b++;
            }
        }
        nums[0] = a;
        nums[1] = b;
        return nums;
    }
}

二、518. 零钱兑换 II

题目链接：https://leetcode.cn/problems/coin-change-ii/description/
思路：本题物品数量无限是完全背包，完全背包求组合数。完全背包物品和背包都是正序，如果求组合数，物品在外，背包在内。如果求排列数，背包在外，物品在内。

class Solution {
    public int change(int amount, int[] coins) {
        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 - coins[i]];
            }
        }
        return dp[amount];
    }
}

三、377. 组合总和 Ⅳ

题目链接：https://leetcode.cn/problems/combination-sum-iv/description/
思路：和上一题类似，也是物品无限使用，是完全背包，但是不同的是求的是排列数。物品和背包都正序，背包在外，物品在内。

class Solution {
    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target+1];
        dp[0] = 1;
        for(int i = 1; i <= target; i++) {
            for(int j = 0; j < nums.length; j++) {
                if(nums[j] > i) continue;
                dp[i] += dp[i - nums[j]];
            }
        }
        return dp[target];
    }
}

四、57. 爬楼梯（第八期模拟笔试）

题目链接：https://kamacoder.com/problempage.php?pid=1067
思路：本题是总楼梯数是背包总数，每次可以爬的楼梯数（1 <= m < n），求有多少种爬楼的方法。所以很明显是完全背包求排列数，爬楼梯的方法1,2和2,1明细是两种方法。所以直接套公式，完全背包求排列数，背包在外，物品在内。背包和物品都正序。
同时推荐一下卡码网，可以练习ACM模式。

import java.lang.*;
import java.util.*;

class Main{
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt(), m = scan.nextInt();
        int[] dp = new int[n+1];
        dp[0] = 1;
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                if(i >= j) {
                    dp[i] += dp[i-j];
                }
            }
        }
        System.out.println(dp[n]);
    } 
}

五、322. 零钱兑换

题目链接：https://leetcode.cn/problems/coin-change/description/
思路：本题是物品数量无限，完全背包。对于完全背包求组合数，物品在外，背包在内，求排列数，背包在外，物品在内。
其他的比如求能装的最大最小个数，物品和背包没有顺序要求，所以在内在外都行，其他的没有了。

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount+1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for(int i = 0; i < coins.length; i++) {
            for(int j = coins[i]; j <= amount; j++) {
                if(dp[j-coins[i]] == Integer.MAX_VALUE) continue;
                dp[j] = Math.min(dp[j], dp[j-coins[i]]+1);
            }
        }
        return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
    }
}