代码随想录算法训练营第三十五天-1049最后一块石头的重量 II、494目标和、474一和零

前言
状态：1049 和昨天那题差不多。494、474。。。☠️动规还是先了解解法。后面刷别的题组的时候再说。
更新

1	24-06-21 初始记录

初步题解

1049 最后一块石头的重量 II

题目链接：(https://leetcode.cn/problems/last-stone-weight-ii)

本题可以抽象成让石头分成尽量相同的两堆，然后进行相撞。即背包大小为总和除以 2，求能放入的最大价值。

确定 dp[i] 的含义：从石头里任取，背包大小为 i，能放入的最大价值。weight[i] = store[i]，value[i] = store[i]。
递推公式：dp[i] = Math.max(dp[i], dp[i - weight[j]] + value[j])。
dp 数组的初始化：dp[0] = 0。
遍历顺序：从后向前遍历。
打印 dp 数组（用于 debug）

public int lastStoneWeightII(int[] stones) {  
    int sum = Arrays.stream(stones).sum();  
  
    int[] dp = new int[sum / 2 + 1];  
  
    for (int stone : stones) {  
        for (int j = dp.length - 1; j >= 0; j--) {  
            if (j >= stone) {  
			    dp[j] = Math.max(dp[j], dp[j - stone] + stone);  
			} 
        }  
    }  
  
    return sum - dp[sum / 2] * 2;  
}

494 目标和

题目链接：(https://leetcode.cn/problems/target-sum)

完全没思路

474 一和零

题目链接：(https://leetcode.cn/problems/ones-and-zeroes)

看不懂，题目都看不懂☠️

看解析

1049 最后一块石头的重量 II

解析：(https://programmercarl.com/1049.最后一块石头的重量II.html)

494 目标和

解析：(https://programmercarl.com/0494.目标和.html)

假设正数集合总和是 left，负数集合总和是 right。总和 sum = left + right。目标值 target = left - right。可以得到 left 即正数之和 = (sum + target)/2。

本题是装满有几种方法。这是一个组合问题，用的解法就和之前不一样。

确定 dp[i] 的含义：填满 i（包括 i）这么大容积的包，有 dp[i] 种方法
递推公式：dp[j] += dp[j - nums[i]]。

已经有一个 1（nums[i]）的话，有 dp[4] 种方法凑成容量为 5 的背包。

已经有一个 2（nums[i]）的话，有 dp[3] 种方法凑成容量为 5 的背包。

已经有一个 3（nums[i]）的话，有 dp[2] 种方法凑成容量为 5 的背包

已经有一个 4（nums[i]）的话，有 dp[1] 种方法凑成容量为 5 的背包

已经有一个 5 （nums[i]）的话，有 dp[0] 种方法凑成容量为 5 的背包

那么凑整 dp[5] 有多少方法呢，也就是把所有的 dp[j - nums[i]] 累加起来。

dp 数组的初始化：dp[0] = 1。假设数组个数为 0，获取 dp[0]，就是 1。
遍历顺序：从后向前遍历。
打印 dp 数组（用于 debug）

public int findTargetSumWays(int[] nums, int target) {  
    int sum = Arrays.stream(nums).sum();  
    if ((sum + target) % 2 == 1) {  
        return 0;  
    }  
  
    if (sum < Math.abs(target)) {  
        return 0;  
    }  
  
    int left = (sum + target) / 2;  
    int[] dp = new int[left + 1];  
    dp[0] = 1;  
    for (int num : nums) {  
        for (int j = dp.length - 1; j >= num; j--) {  
		    // 这里比较难理解
            dp[j] += dp[j - num];  
        }  
    }  
  
    System.out.println(Arrays.toString(dp));  
  
    return dp[left];  
}

474 一和零

解析：(https://programmercarl.com/0474.一和零.html)

确定 dp[i][j] 的含义：最多有 i 个 0 和 j 个 1 的 strs 的最大子集的大小为 dp[i][j]。物品的重量是 0 的个数，1 的个数。价值就是 1。（难点在二维数组。。反正看了解析又感觉懂了，自己写又不会☠️）
递推公式：dp[i][j] = Math.max(dp[i][j], dp[i - x][j - y]) + 1。
dp 数组的初始化：dp[0][0] = 0。
遍历顺序：从后向前遍历。
打印 dp 数组（用于 debug）

public int findMaxForm(String[] strs, int m, int n) {  
    int[][] dp = new int[m + 1][n + 1];  
  
    // 这里x计算0的数量， y计算1的数量  
    int x, y;  
    for (String str : strs) {  
        x = 0;  
        y = 0;  
        char[] chars = str.toCharArray();  
        for (char c : chars) {  
            if (c == '0') {  
                x++;  
            } else {  
                y++;  
            }  
        }  
  
        for (int i = m; i >= 0; i--) {  
            for (int j = n; j >= 0; j--) {  
                if (i >= x && j >= y) {  
                    dp[i][j] = Math.max(dp[i][j], dp[i - x][j - y] + 1);  
                }  
            }  
        }  
    }  
    return dp[m][n];  
}