代码随想录算法训练营第三十六天

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

题目链接 最后一块石头的重量II

题解

class Solution {
    public int lastStoneWeightII(int[] stones) {
        int len = stones.length;
        int sum = 0;
        for(int i = 0;i<len;i++) sum += stones[i];
        int target = sum / 2;
        int[] dp = new int[target + 1];
        for(int i = 0;i<len;i++){
            for(int j = target;j>=stones[i];j--){
                dp[j] = Math.max(dp[j],dp[j-stones[i]] + stones[i]);
            }
        }
        int max_value = dp[target];
        return sum - max_value * 2;
    }
}

解题思路

这段代码解决的是 "最后一块石头的重量 II" 问题，这是一个典型的动态规划问题，本质上可以转化为 0-1 背包问题。

算法思路解析：

1. 问题转化：将石头分成两堆，使两堆的重量尽可能接近总和的一半。这样两堆石头碰撞后剩下的重量就是最小可能值。
2. 动态规划思路：
   • 计算所有石头的总重量 sum
   • 目标是找到总和不超过 sum/2 的最大子集和
   • 使用 0-1 背包的动态规划方法求解这个最大子集和

代码解释：

• sum：计算所有石头的总重量
• target：总重量的一半，作为背包的最大容量
• dp[j]：表示容量为 j 的背包能装下的最大石头重量
• 内层循环采用倒序遍历j，是为了避免同一石头被多次使用（0-1 背包特性）
• 最终结果sum - max_value * 2表示两堆石头碰撞后剩余的最小重量

LeetCode.494 目标和

题目链接 目标和

题解

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        int len = nums.length;
        for(int i = 0;i<len;i++) sum += nums[i];
        if ((target + sum) % 2 == 1) return 0;
         if (Math.abs(target) > sum) return 0;
        int n = (sum + target) / 2;
        // 能凑成i容量的dp[i]种方法
        int[] dp = new int[n+1];
        dp[0] = 1;
        for(int i = 0;i<len;i++){
            for(int j = n;j>=nums[i];j--){
                dp[j] += dp[j - nums[i]];
            }
        } 
        return dp[n];
    }
}

解题思路

这段代码解决的是 "目标和" 问题，即通过给数组中的每个数字添加 "+" 或 "-"，使得它们的和等于目标值 target，计算有多少种不同的方法。

算法思路解析：

1. 问题转化：假设数组中添加 "+" 的元素和为sumA，添加 "-" 的元素和为sumB，则有：

   • sumA - sumB = target
   • sumA + sumB = sum（数组总和）
     两式相加可得 2*sumA = target + sum，即 sumA = (target + sum) / 2

2. 关键判断：

   • 如果(target + sum)是奇数，无法整除，直接返回 0
   • 如果target的绝对值大于总和sum，也返回 0

3. 动态规划思路：

   • 问题转化为：从数组中选取若干元素，使其和等于sumA，计算有多少种选法
   • 这是一个典型的 "子集和计数" 问题，可用 0-1 背包的动态规划方法解决

代码解释：

• sum：计算数组所有元素的总和
• n：即上述的sumA，表示需要凑出的目标和
• dp[i]：表示能凑成和为 i 的方法总数
• 初始化dp[0] = 1：表示凑成和为 0 的方法有 1 种（什么都不选）
• 内层循环倒序遍历，避免同一元素被重复使用
• 最终结果dp[n]就是能凑成目标和的方法总数

LeetCode.474 一和零

题目链接 一和零

题解

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int[][][] dpArr = new int[strs.length][m + 1][n + 1];

        int zeroNum = 0;
        int oneNum = 0;
        for (char c : strs[0].toCharArray()) {
            if (c == '0') {
                zeroNum++;
            } else {
                oneNum++;
            }
        }
        for (int j = zeroNum; j <= m; j++) {
            for (int k = oneNum; k <= n; k++) {
                dpArr[0][j][k] = 1;
            }
        }
        for (int i = 1; i < strs.length; i++) {
            zeroNum = 0;
            oneNum = 0;
            for (char c : strs[i].toCharArray()) {
                if (c == '0') {
                    zeroNum++;
                } else {
                    oneNum++;
                }
            }
            for (int j = 0; j <= m; j++) {
                for (int k = 0; k <= n; k++) {
                    if (j >= zeroNum && k >= oneNum) {
                        dpArr[i][j][k] = Math.max(dpArr[i - 1][j][k], dpArr[i - 1][j - zeroNum][k - oneNum] + 1);
                    } else {
                        dpArr[i][j][k] = dpArr[i - 1][j][k];
                    }
                }
            }
        }
        return dpArr[dpArr.length - 1][m][n];
    }
}

解题思路

这段代码解决的是 "一和零" 问题，即在给定 0 和 1 的最大数量限制 (m 和 n) 的情况下，从字符串数组中选出最多数量的字符串，使这些字符串中包含的 0 总数不超过 m，1 总数不超过 n。

算法思路解析：

这是一个典型的二维 0-1 背包问题：

• 每个字符串可以看作一个物品
• 每个物品有两个 "重量" 属性：0 的数量和 1 的数量
• 背包的两个容量限制分别是 m (0 的最大数量) 和 n (1 的最大数量)
• 目标是选择最多数量的物品 (字符串) 而不超过背包容量

代码解释：

1. 三维 DP 数组定义：dpArr[i][j][k]表示在前 i 个字符串中，使用不超过 j 个 0 和 k 个 1 时能选取的最大字符串数量

2. 初始化处理：

   • 计算第一个字符串中 0 和 1 的数量
   • 对于能容纳第一个字符串的所有 (j,k) 组合，初始化为 1 (表示选择第一个字符串)

3. 状态转移：

   • 对每个字符串，先计算其包含的 0 和 1 的数量
   • 对每种可能的 0 和 1 的数量限制 (j,k)：
     • 如果当前字符串可以被容纳 (j>= 0 的数量且 k >= 1 的数量)，则取 "不选当前字符串" 和 "选当前字符串" 两种情况的最大值
     • 否则，只能继承不选当前字符串的结果

4. 最终结果：dpArr[strs.length - 1][m][n]表示考虑所有字符串后，在 m 和 n 限制下能选取的最大字符串数量