完全背包和01背包的二维dp模板和一维dp模板

01背包

未优化的二维数组形式，j 遍历顺序、逆序皆可；但优化后的一维数组形式 j 必须逆序遍历！

//二维数组形式
for(int i=1;i<=n;i++)
{
    for(int j=w[i];j<=V;j++)
    {
        dp[i][j]=max(dp[i−1][j−w[i]]+c[i],dp[i−1][j]]);
    }   
}

//一维数组形式
for(int i=1;i<=n;i++)
{
    for(int j=V;j>=w[i];j--)    //逆序遍历
    {
        dp[j]=max(dp[j−w[i]]+c[i],dp[j]]);
    }   
}

完全背包

i 的枚举方向从1到n，j 的枚举方向从w[i]到V（顺序遍历！）
01背包与完全背包的一维数组形式的状态转移方程相同，但 01背包采用逆序遍历，完全背包采用顺序遍历。

//二维数组形式
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= C; j++) {
        for (int k = 0; k * w[i] <= j; k++) {
            dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - k * w[i]] + k * v[i]);
        }
    }
}

//一维数组形式
for(int i=1;i<=n;i++)
{
    for(int j=w[i];j<=V;j++)    //顺序遍历
    {
        dp[j]=max(dp[j−w[i]]+c[i],dp[j]]);
    }   
}

硬币组合数

硬币。给定数量不限的硬币，币值为25分、10分、5分和1分，编写代码计算n分有几种表示法。(结果可能会很大，你需要将结果模上1000000007)
示例1:
输入: n = 5
输出：2
解释: 有两种方式可以凑成总金额:
5=5
5=1+1+1+1+1
示例2:
输入: n = 10
输出：4
解释: 有四种方式可以凑成总金额:
10=10
10=5+5
10=5+1+1+1+1+1
10=1+1+1+1+1+1+1+1+1+1
说明：
注意:
你可以假设：
0 <= n (总金额) <= 1000000

分析

由于无限数量硬币的选择，应该是一个完全背包问题
dp 数组建立：dp[i][j] 表示 i 种硬币组成面值为 j 时的方法数

考虑 base case

dp[0][j] 0 种硬币组成面值 j，不可能有方案，因此是 0， java 初始化时数组是 0，不用特殊处理

dp[i][0] 多种硬币组成面值 0，只有一种方案，就是一枚也不选

状态转移方程：

dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i])

其中 dp[i - 1][j] 表示当前硬币不选，那么由 i - 1 种组成面值 j

dp[i][j - coins[i]) 表示当前硬币选了，那么还需要组成面额为 j - coins[i], 这都是已要组成的面值大于当前硬币值为前提的。

因此可以先写出一个二维 dp 的代码，再进一步进行优化，状态压缩

二维的dp

class Solution {
    public int waysToChange(int n) {
        int[] nums = new int[4];
        nums[0] = 1;
        nums[1] = 5;
        nums[2] = 10;
        nums[3] = 25;
        int[][] dp = new int[5][n+1];
        dp[0][0]=1;
        dp[1][0]=1;
        dp[2][0]=1;
        dp[3][0]=1;
        dp[4][0]=1;
        for(int i=1;i<=4;i++){
            for(int j = 1; j <= n; j++) {
                if(j>=nums[i-1]){
                     // 当前硬币可以不选，也可以选择
                    dp[i][j] = (dp[i-1][j] + dp[i][j-nums[i-1]])%1000000007;
                }else{
                     // 当前硬币只能不选
                    dp[i][j] = dp[i-1][j];
                }
                
            }
        }
        return dp[4][n];
    }
}

进一步一维 dp ，从状态转移方程可以看出，dp[i][j] 仅仅和 dp[i-1]的状态有关，所以可以压缩为 1 维

class Solution {
    public int waysToChange(int n) {
        int[] nums = new int[4];
        nums[0] = 1;
        nums[1] = 5;
        nums[2] = 10;
        nums[3] = 25;
        int[] dp = new int[n+1];
        dp[0]=1;
        for(int i=1;i<=4;i++){
            for(int j = 1; j <= n; j++) {
                if(j>=nums[i-1]){
                    dp[j] = (dp[j] + dp[j-nums[i-1]])%1000000007;
                }
            }
        }
        return dp[n];
    }
}

零钱兑换

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。
示例 1：
输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1

示例 2：
输入：coins = [2], amount = 3
输出：-1
示例 3：
输入：coins = [1], amount = 0
输出：0

提示：
1 <= coins.length <= 12
1 <= coins[i] <= 231 - 1
0 <= amount <= 104

完全背包3层循环，遍历每一个k

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[][] dp = new int[coins.length+1][amount+1];
        int n = coins.length;
         for(int[] a: dp) {
                Arrays.fill(a, amount+1);  // 初始化
         }
        dp[0][0] = 0; // 合法的初始化，其他dp[0][j]均不合法
        for(int i=1;i<=n;i++){
            for(int j=0;j<=amount;j++){
                int k = 0;
                while (j - k * coins[i - 1] >= 0) {
                    dp[i][j] = Math.min(dp[i][j], dp[i - 1][j - k * coins[i - 1]] + k);
                    k ++;
                }
            }
        }
        return dp[n][amount]==amount+1?-1:dp[n][amount];
    }
}

完全背包2维dp，两层循环，利用完全背包二维的公式

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[][] dp = new int[coins.length+1][amount+1];
        int n = coins.length;
         for(int[] a: dp) {
            Arrays.fill(a, amount+1);  // 初始化
         }
        dp[0][0] = 0; // 合法的初始化，其他dp[0][j]均不合法
        for(int i=1;i<=n;i++){
            for(int j=0;j<=amount;j++){
                if(j>=coins[i-1]){
                    dp[i][j] = Math.min(dp[i-1][j],dp[i][j-coins[i-1]]+1);
                }else{
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        return dp[n][amount]==amount+1?-1:dp[n][amount];
    }
}

完全背包1维dp，两层循环，利用完全背包1维的公式

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount+1];
        int n = coins.length;{
        Arrays.fill(dp, amount+1);  // 初始化
        dp[0] = 0; // 合法的初始化
        for(int i=1;i<=n;i++){
            for(int j=0;j<=amount;j++){
                if(j>=coins[i-1]){
                    dp[j] = Math.min(dp[j],dp[j-coins[i-1]]+1);
                }
            }
        }
        return dp[amount]==amount+1?-1:dp[amount];
    }
}
}

完全平方数

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

示例 1：
输入：n = 12
输出：3
解释：12 = 4 + 4 + 4
示例 2：

输入：n = 13
输出：2
解释：13 = 4 + 9
就是先找到小于n的完全平方数，他们就是物品

完全背包1维dp，两层循环，利用完全背包1维的公式

class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n+1];
        Arrays.fill(dp,n+1);
        dp[0]=0;
        int sum = 1;
        while(sum*sum<=n){
            sum++;
        }
        for(int i=1;i<=sum;i++){
            for(int j=0;j<=n;j++){
                if(j>=i*i){
                    dp[j] = Math.min(dp[j],dp[j-i*i]+1);
                }
            }
        }
        return dp[n];
    }
}

精简一下

class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n+1];
        Arrays.fill(dp,n+1);
        dp[0]=0;
        for(int i=1;i*i<=n;i++){
            for(int j=1;j<=n;j++){
                if(j>=i*i){
                    dp[j] = Math.min(dp[j],dp[j-i*i]+1);
                }
            }
        }
        return dp[n];
    }
}

分割等和子集

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
示例 1：
输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。

示例 2：
输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。

就是这堆数组能不能装总和的一半-01背包

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        int l = nums.length;
        for(int i=0;i<l;i++){
            sum+=nums[i];
        }
        if(sum%2==1){
            return false;
        }
        sum = sum/2;
        boolean[][] dp = new boolean[l+1][sum+1];
        dp[0][0]=true;
        for(int i=1;i<=l;i++){
            for(int j=1;j<=sum;j++){
                if(j>=nums[i-1]){
                    dp[i][j]=dp[i-1][j]||dp[i-1][j-nums[i-1]];
                }else{
                    dp[i][j]=dp[i-1][j];
                }
            }
        }
        return dp[l][sum];
    }
}

一和零

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。
如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。
示例 1：
输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
输出：4
解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。
其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。

示例 2：
输入：strs = ["10", "0", "1"], m = 1, n = 1
输出：2
解释：最大的子集是 {"0", "1"} ，所以答案是 2 。

提示：
1 <= strs.length <= 600
1 <= strs[i].length <= 100
strs[i] 仅由 '0' 和 '1' 组成
1 <= m, n <= 100

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int l = strs.length;
        int[][][] dp = new int[l+1][m+1][n+1];
        dp[0][m][n] = 0;
        for(int k=1;k<=l;k++){
            int zeroNum = getZero(strs[k-1]);
            int oneNum = getOne(strs[k-1]);
            for(int i=0;i<=m;i++){
                for(int j=0;j<=n;j++){
                    if(i>=zeroNum&&j>=oneNum){
                        dp[k][i][j] = Math.max(dp[k-1][i][j],dp[k-1][i-zeroNum][j-oneNum]+1);
                    }else{
                        dp[k][i][j] = dp[k-1][i][j];
                    }
                }
            }
        }
        return dp[l][m][n];
    }
    public int getZero(String str) {
       return str.length() - str.replaceAll("0","").length();
    }
    public int getOne(String str) {
        return str.length() - getZero(str);
    }
}

滚动数组 从后往前滚动
由于 dp[i][][] 的每个元素值的计算只和 dp[i−1][][] 的元素值有关，因此可以使用滚动数组的方式，去掉 dp 的第一个维度，将空间复杂度优化O(mn)。实现时，内层循环需采用倒序遍历的方式，这种方式保证转移来的是
dp[i−1][][] 中的元素值。

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int l = strs.length;
        int[][] dp = new int[m+1][n+1];
        dp[0][0] = 0;
        for(int k=1;k<=l;k++){
            int zeroNum = getZero(strs[k-1]);
            int oneNum = getOne(strs[k-1]);
            for(int i=m;i>=zeroNum;i--){
                for(int j=n;j>=oneNum;j--){
                    if(i>=zeroNum&&j>=oneNum){
                        dp[i][j] = Math.max(dp[i][j],dp[i-zeroNum][j-oneNum]+1);
                    }
                }
            }
        }
        return dp[m][n];
    }
    public int getZero(String str) {
       return str.length() - str.replaceAll("0","").length();
    }
    public int getOne(String str) {
        return str.length() - getZero(str);
    }
}

完全背包顺序不同的序列被视作不同的组合。

给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。
题目数据保证答案符合 32 位整数范围。
示例 1：
输入：nums = [1,2,3], target = 4
输出：7
解释：
所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意，顺序不同的序列被视作不同的组合。

示例 2：
输入：nums = [9], target = 3
输出：0

class Solution {
    public int combinationSum4(int[] nums, int target) {
        int l = nums.length;
        int[] dp = new int[target+1];
        dp[0]=1;
        for(int j = 1; j <= target; j++) {//为啥先遍历背包容量就是顺序不同的序列被视作不同的组合。
            for(int i=1;i<=l;i++){
                if(j>=nums[i-1]){
                    dp[j] = dp[j] + dp[j-nums[i-1]];
                }
            }
        }
        return dp[target];
    }
}