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

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 背包问题。

算法思路解析：

代码解释：

• 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，计算有多少种不同的方法。

算法思路解析：

代码解释：

• 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 的最大数量)
• 目标是选择最多数量的物品 (字符串) 而不超过背包容量

代码解释：