动态规划（背包常见问题）

常见的背包问题有0 1 背包问题和完全背包问题，对于一个要装入背包的元素来说，如果他只能使用一次就是0 1背包问题，如果能使用多次则就是完全背包问题。此外这里使用的01 背包是1维的形式，1维的01 背包只能先遍历物品，再遍历背包，并且保证内层循环是倒叙的进行遍历。

类型一（能否装满背包）

dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);

416. 分割等和子集

题目连接：https://leetcode.cn/problems/partition-equal-subset-sum/
有人看到这个题就会说了，这哪里看着像背包问题背包在哪里，就算你把物品看成nums，背包不知道怎么获取。
但是你需要提取出四点信息才能确定这是01 背包问题
背包的体积为sum / 2
背包要放入的商品（集合里的元素）重量为 元素的数值，价值也为元素的数值
背包如果正好装满，说明找到了总和为 sum / 2 的子集。
背包中每一个元素是不可重复放入。
题目中问的是分割等和的子集，就是把一个集合一分为二看是否两个子集相等就完了。

class Solution {
    public boolean canPartition(int[] nums) {
        int sum=0;
        for(int i=0;i<nums.length;i++){
            sum+=nums[i];
        }
        if(sum%2!=0) return false;
        int target=sum/2;
        int[] dp=new int[target+1];
        dp[0]=0;
        for(int i=0;i<nums.length;i++){
            for(int j=target;j>=nums[i];j--){
                dp[j]=Math.max(dp[j],dp[j-nums[i]]+nums[i]);
            }
        }
        return dp[target]==target;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

1049. 最后一块石头的重量 II

题目连接：https://leetcode.cn/problems/last-stone-weight-ii/
顺便提一句这个题是完美世界的笔试题
题中说道随机拿出石头相撞最后要么全部撞碎，要么只剩一块，全部撞碎的情况是不是就分成两等份了？那如果剩一块呢，剩一块可以看成两份相等的石头多一块不就完了，换汤不换药。
这里还是求和然后除了一半，注意内层循环是逆序的。

class Solution {
    public int lastStoneWeightII(int[] stones) {
        int sum=0;
        for(int i=0;i<stones.length;i++){
            sum+=stones[i];
        }
        int target=sum/2;
        int[] dp=new int[target+1];
        //dp[j]表示容量（这里说容量更形象，其实就是重量）为j的背包，最多可以背dp[j]这么重的石头。
        for(int i=0;i<stones.length;i++){
            for(int j=target;j>=stones[i];j--){
                dp[j]=Math.max(dp[j],dp[j-stones[i]]+stones[i]);
            }
        }
        return sum-dp[target]-dp[target];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

类型二（装满背包的方式有几种）

dp[j] += dp[j - nums[i]]

494. 目标和

题目连接：https://leetcode.cn/problems/target-sum/
思路：一部分数是正数，一部分数是负数。两部分数相加等于target
假设加法的总和为x，那么减法对应的总和就是sum - x。

所以我们要求的是 x - (sum - x) = target

x = (target + sum) / 2

此时问题就转化为，装满容量为x背包，有几种方法。

大家看到(target + sum) / 2 应该担心计算的过程中向下取整有没有影响。
有影响的！如果有余数的话组不成那就返回0；

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum=0;
        for(int i=0;i<nums.length;i++){
            sum+=nums[i];
        }
        if((target+sum)%2!=0) return 0;
        int bagesize=(target+sum)/2;
        if(bagesize<0) bagesize=-bagesize;
        int[] dp=new int[bagesize+1];
        //组成容量j有dp【j】种方法
         dp[0]=1;//容量为0的组成方法就一种就是放入0
        for(int i=0;i<nums.length;i++){
            for(int j=bagesize;j>=nums[i];j--){
                dp[j]+=dp[j-nums[i]];
            }
        }
        return dp[bagesize];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

518. 零钱兑换 II

题目连接：https://leetcode.cn/problems/coin-change-2/
完全背包解法，注意初始化dp【0】，第二层for循环从coins[i]开始

class Solution {
    public int change(int amount, int[] coins) {
        int[] dp=new int[amount+1];
        //代表了组成amount金额所需要的硬币数
        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];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

377. 组合总和 Ⅳ

题目连接：https://leetcode.cn/problems/combination-sum-iv/
思路：上面两个题都没有讨论关于顺序的问题，只要组成特定背包的组合，可这个题就不一样了，这个题要求的就是排列。
如果求组合数就是外层for循环遍历物品，内层for遍历背包。
如果求排列数就是外层for遍历背包，内层for循环遍历物品。
如果把遍历nums（物品）放在外循环，遍历target的作为内循环的话，举一个例子：计算dp[4]的时候，结果集只有 {1,3} 这样的集合，不会有{3,1}这样的集合，因为nums遍历放在外层，3只能出现在1后面！
所以本题求排列，先遍历背包再遍历物品

class Solution {
    public int combinationSum4(int[] nums, int target) {
        int[] dp=new int[target+1];
        dp[0]=1;
        for(int i=0;i<=target;i++){
            for(int j=0;j<nums.length;j++){
                if(i>=nums[j]){
                    dp[i]+=dp[i-nums[j]];
                }
                
            }
        }
        return dp[target];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

70. 爬楼梯

题目连接：https://leetcode.cn/problems/climbing-stairs/
思路：看了以上的题之后现在想想这个经典的爬楼梯问题，要求走n个台阶的方法，一个可以一个也可以两个，比如爬三个台阶可以先1后2，也可以先2后1步，这不就是一个完全背包求排列的问题吗！target就是n也就是说背包的容量就是n，那么物品呢，物品就是1或者2呀，可以放1这个物品，也可以放2这个物品呀，1或者2可以用无限次，现在是不是豁然了许多。

class Solution {
    public int climbStairs(int n) {
        int[] dp=new int[n+1];
        dp[0]=1;
        for(int i=0;i<=n;i++){
            for(int j=1;j<=2;j++){
                if(i>=j){
                    dp[i]+=dp[i-j];
                }
            }
        }
        return dp[n];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

类型三（装满背包最大价值）

474. 一和零

问背包装满最大价值：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
题目连接：https://leetcode.cn/problems/ones-and-zeroes/
思路：在这个题提取背包思想还是我个人感觉不太好想，首先题意你想要找m个0和n个1从一个集合的子集中去找，而且这个子集的长度要求最大。
m个0和n个1可以看成是背包的最大的容量，物品呢就是字符串数组里面的每个字符串，再具体一点物品是每一个字符串里面0和1的个数，所以每个字符串0和1的个数统计是必要的，还有这是个01 背包问题只不过是二维维度的，记得第二个for循环是逆序的。

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int[][] dp=new int[m+1][n+1];
        //dp函数代表m个0和n个1的最大子集的长度
        for(String s:strs){
            char[] arr=s.toCharArray();
            int zeroNum=0,oneNum=0;
            for(char c:arr){
                if(c=='0') zeroNum++;
                else oneNum++;
            }
            for(int i=m;i>=zeroNum;i--){
                for(int j=n;j>=oneNum;j--){
                    dp[i][j]=Math.max(dp[i][j],dp[i-zeroNum][j-oneNum]+1);
                }
            }
        }
        return dp[m][n];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

类型四（求装满背包的所有物品的最小个数）

问装满背包所有物品的最小个数：dp[j] = min(dp[j - coins[i]] + 1, dp[j]);

322. 零钱兑换

题目连接：https://leetcode.cn/problems/coin-change/
思路：首先这是个完全背包问题（硬币无限），for循环都是正序，这里求得最小值，无所谓排列组合，然后套用公式，记得物品和背包容量的比较要看能不能装下

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp=new int[amount+1];
        Arrays.fill(dp,amount+1);
        dp[0]=0;
        for(int i=0;i<coins.length;i++){
            for(int j=coins[i];j<=amount;j++){
                if(j>=coins[i]){
                    dp[j]=Math.min(dp[j],dp[j-coins[i]]+1);
                }else{
                    continue;
                }
            }
        }
        return dp[amount]==amount+1?-1:dp[amount];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

279. 完全平方数

题目连接：https://leetcode.cn/problems/perfect-squares/
思路：题中每个数可以用多次，完全背包问题
n就是target，那么物品呢？物品就是每个平方数，例如1,4，9,16。再看题目中的数据限制，1到10的4次方，那么100个平方数就够了。然后呢划重点最少数量！最少数量！最少数量！

class Solution {
    public int numSquares(int n) {
        int[] dp=new int[n+1];
        int[] arr=new int[100];
        for(int i=0;i<100;i++){
            arr[i]=(int)Math.pow(i+1,2);
        }
        Arrays.fill(dp,n+1);
        dp[0]=0;
        for(int i=0;i<arr.length;i++){
            for(int j=arr[i];j<=n;j++){
                if(j>=arr[i]){
                    dp[j]=Math.min(dp[j],dp[j-arr[i]]+1);
                }
            }
        }
        return dp[n];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19