代码随想录算法训练营 | 1049. 最后一块石头的重量 II，494. 目标和，474.一和零

1049. 最后一块石头的重量 II
题目链接：1049. 最后一块石头的重量 II
文档讲解︰代码随想录(programmercarl.com)
视频讲解︰最后一块石头的重量 II
日期：2024-10-10

想法：这这么会是分割等和子集一类的问题。。。
Java代码如下：

class Solution {
    public int lastStoneWeightII(int[] stones) {
        if(stones == null || stones.length == 0) return 0;
        int sum = 0;
        for(int num : stones) {
            sum += num;
        }
        int target = sum / 2;
        int[] dp = new int[target + 1];

        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 - 2 * dp[target];
    }
}

494. 目标和
题目链接：494. 目标和
文档讲解︰代码随想录(programmercarl.com)
视频讲解︰目标和
日期：2024-10-10

想法：假设加法的总和为bagSize，那么减法对应的总和就是sum - bagSize,所以要求的是 bagSize - (sum - bagSize) = target; bagSize = (target + sum) / 2
此时问题就转化为，用nums装满容量为bagSize的背包，有几种方法。

1. dp的意思是有多少种组合满足，二维数组dp[i][j]表示nums种0到i的数相加得到j的组合数为dp[i][j]，
2. 递推公式：第一种情况dp[i - 1][j]表示不加上nums[i]这个数时能得到和为j的组合数，第二种情况要加上nums[i]，先就得腾出j - nums[i]的空间，看此时dp[i - 1][j - nums[i]]有多少组合，这个组合数就是加上nums[i]总和为j的组合数。
   3.初始化：初始化第一行第一列，第一行j刚好等于nums[0]时会有1种（要nums[0]），第一列的话如果nums[0]不是0，那么就1种组合法（不要nums[0]），如果nums[0]是0的话就会麻烦点，那么就2^1 = 2种组合法（不要nums[0],要nums[0]都行），第一列第二个如果也是0，就会有2^2 = 4种（不要nums[0],要nums[0]，不要nums[1],要nums[1]都行），所以有多少个0，就有2多少次方个方法。
   4.遍历顺序：上下左右，左右上下都行。
   5.举例推导dp数组

Java代码如下：

//二维数组
class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for(int num : nums) {
            sum += num;
        }
        if((sum + target) % 2 != 0) return 0;
        if(Math.abs(target) > sum) return 0;
        int bagSize = (sum + target) / 2;

        int[][] dp = new int[nums.length][bagSize + 1];
        int zeroN = 0;
        
        if(nums[0] <= bagSize) dp[0][nums[0]] = 1;
        for(int i = 0; i < nums.length; i++) {
            if(nums[i] == 0) {
                zeroN++;
            }
            dp[i][0] = (int) Math.pow(2, zeroN);
        }

        for(int i = 1; i < nums.length; i++) {
            for(int j = 1; j <= bagSize; j++) {
                if(j >= nums[i]) {
                    dp[i][j] = dp[i - 1][j] + dp[i - 1][j -nums[i]];
                }else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[nums.length - 1][bagSize];
    }
}

//一维数组
class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for(int num : nums) {
            sum += num;
        }
        if((sum + target) % 2 != 0) return 0;
        if(Math.abs(target) > sum) return 0;
        int bagSize = (sum + target) / 2;

        int[] dp = new int[bagSize + 1];

        dp[0] = 1;

        for(int i = 0; i < nums.length; i++) {
            for(int j = bagSize; j >= nums[i]; j--) {
                dp[j] += dp[j -nums[i]];
            }
        }
        return dp[bagSize];
    }
}

总结：一维数组的形式初始化只需要dp[0] = 1就行了，想象下nums[0]为0时，j = 0时递推公式dp[j] += dp[j -nums[i]];依旧可以用，此时相当于dp[0]+dp[0] = 2了。

474.一和零
题目链接：474.一和零
文档讲解︰代码随想录(programmercarl.com)
视频讲解︰一和零
日期：2024-10-10

Java代码如下：

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int[][] dp = new int[m + 1][n + 1];
        int oneNum, zeroNum;
        for (String str : strs) {
            oneNum = 0;
            zeroNum = 0;
            for (char ch : str.toCharArray()) {
                if (ch == '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];
    }
}