力扣爆刷第73天--动态规划

力扣爆刷第73天–动态规划

零、背包问题总纲：

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

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

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

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

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

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

一、416. 分割等和子集

题目链接：https://leetcode.cn/problems/partition-equal-subset-sum/description/
思路：等和分割子集，就是计算出总和的一半，然后把所有元素往里面装看最大值是否能达到一半，能达到即可划分，这就转换成一个背包问题了。

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;
        sum = sum / 2;
        int[] dp = new int[sum+1];
        for(int i = 0; i < nums.length; i++) {
            for(int j = sum; j >= nums[i] ; j--) {
                dp[j] = Math.max(dp[j], dp[j-nums[i]] + nums[i]);
            }
        }
        return dp[sum] == sum;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

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

题目链接：https://leetcode.cn/problems/last-stone-weight-ii/description/
思路：本题说石头之间两两抵消，求最后余数，其实就是把石头划分为两堆，然后计算差值，差值即为最后一块石头的重量，那么求一半和的背包问题，即可。

class Solution {
    public int lastStoneWeightII(int[] stones) {
        int sum = 0;
        for(int i = 0; i < stones.length; i++) {
            sum += stones[i];
        }
        int temp = sum / 2;
        int[] dp = new int[temp + 1];
        for(int i = 0; i < stones.length; i++) {
            for(int j = temp; j >= stones[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j-stones[i]] + stones[i]);
            }
        } 
        return sum - 2*dp[temp];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16