1049. 最后一块石头的重量 II
有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。
每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
如果 x == y，那么两块石头都会被完全粉碎；
如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。
示例 1：
输入：stones = [2,7,4,1,8,1]
输出：1
解释：
组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]，
组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]，
组合 2 和 1，得到 1，所以数组转化为 [1,1,1]，
组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。
示例 2：
输入：stones = [31,26,33,21,40]
输出：5
方法一：一维数组
class Solution {
public int lastStoneWeightII(int[] stones) {
int sum = 0;
for (int i : stones) {
sum += i;
}
int target = sum >> 1;
//初始化dp数组
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];
}
}
这段Java代码是一个解决方案，用于解决“最后的石头重量II”问题。这个问题源于LeetCode上的1049题。问题是这样的：有一堆石头，每个石头有一定的重量。在每一轮操作中，你可以选择任意两块石头然后将它们一起粉碎，新石头的重量等于两者之差的绝对值。最终，所有的石头都会变成一堆石头，而最后一块石头的重量就是这些石头的重量之和。任务是找到一种操作策略，使得最后这块石头的重量尽可能小。
代码解析
计算总重量：首先，遍历输入数组
stones，计算所有石头的总重量，并存储在变量sum中。确定目标重量：因为最终目标是最小化两堆石头重量之差，所以理论上最优情况是一堆石头的总重量尽可能接近总重量的一半。因此，设定目标重量
target为sum除以2（使用右移运算符>> 1等同于除以2，用于快速整除）。初始化动态规划数组：创建一个长度为
target + 1的数组dp，用于动态规划计算。dp[j]表示能否通过选择某些石头使总重量达到j，并且这个总重量尽可能接近target。填充动态规划数组：
- 双层循环遍历每个石头和每个可能的目标重量。外层循环遍历石头，内层循环从
target反向遍历到当前石头的重量。这是因为在考虑加入当前石头时，我们总是从最大的可能贡献开始尝试（即直接达到或接近目标重量）。 - 对于每个石头，如果它不超重（即
j >= stones[i]），则更新dp[j]为不包含当前石头能达到的最大重量dp[j]与包含当前石头能达到的新重量dp[j - stones[i]] + stones[i]之间的较大值。这体现了动态规划中的决策过程：要么选取当前石头，要么不选取。
- 双层循环遍历每个石头和每个可能的目标重量。外层循环遍历石头，内层循环从
计算结果：最后，由于
dp[target]代表了最接近sum/2的最大可能重量，因此两堆石头的重量之差即为sum - 2 * dp[target]。这是因为总重量是sum，最优情况下两堆重量尽量平衡，即一边为dp[target]，另一边为sum - dp[target]，但为了求差值最小，我们直接用总重量减去两倍的dp[target]。
小结
这段代码通过动态规划的方法，有效地解决了“最后的石头重量II”问题，寻找了一种策略来最小化最终剩余石头的重量。
方法二：二维数组
class Solution {
public int lastStoneWeightII(int[] stones) {
int sum = 0;
for (int s : stones) {
sum += s;
}
int target = sum / 2;
//初始化，dp[i][j]为可以放0-i物品，背包容量为j的情况下背包中的最大价值
int[][] dp = new int[stones.length][target + 1];
//dp[i][0]默认初始化为0
//dp[0][j]取决于stones[0]
for (int j = stones[0]; j <= target; j++) {
dp[0][j] = stones[0];
}
for (int i = 1; i < stones.length; i++) {
for (int j = 1; j <= target; j++) {//注意是等于
if (j >= stones[i]) {
//不放:dp[i - 1][j] 放:dp[i - 1][j - stones[i]] + stones[i]
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - stones[i]] + stones[i]);
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
System.out.println(dp[stones.length - 1][target]);
return (sum - dp[stones.length - 1][target]) - dp[stones.length - 1][target];
}
}
这段代码实现了一个解决“最后一块石头的重量 II”问题的算法。这个问题可以转换成一个背包问题，下面是对代码的详细解释：
题目描述
有一堆石头，每个石头都有一个正整数的重量。每次选择两块石头进行碰撞，重量大的石头会减少重量小的石头的重量。最后剩下的石头最小可能的重量是多少？
解决思路
将石头分成两堆，使得两堆的重量差最小。为了实现这个目标，我们可以将这个问题看作是一个“0/1 背包问题”。
代码解释
计算总重量
sumint sum = 0; for (int s : stones) { sum += s; }计算所有石头的总重量
sum。计算目标重量
targetint target = sum / 2;计算背包容量的目标值
target，即总重量的一半。这是为了尽量使两堆石头的重量接近。初始化动态规划数组
dpint[][] dp = new int[stones.length][target + 1];创建一个二维数组
dp，dp[i][j]表示前i个石头中能够放入容量为j的背包中的最大重量。初始化第一行
for (int j = stones[0]; j <= target; j++) { dp[0][j] = stones[0]; }初始化第一行，即只考虑第一个石头。如果背包容量大于等于第一个石头的重量，那么可以放入这个石头。
填充动态规划数组
dpfor (int i = 1; i < stones.length; i++) { for (int j = 1; j <= target; j++) { if (j >= stones[i]) { dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - stones[i]] + stones[i]); } else { dp[i][j] = dp[i - 1][j]; } } }填充
dp数组。对于每个石头i和每个可能的背包容量j，我们有两种选择：- 不放入当前石头：
dp[i - 1][j] - 放入当前石头：
dp[i - 1][j - stones[i]] + stones[i]
取两者的最大值。
- 不放入当前石头：
计算并返回结果
return (sum - dp[stones.length - 1][target]) - dp[stones.length - 1][target];最后计算两个堆的重量差并返回。
sum - dp[stones.length - 1][target]是剩下的石头的总重量，减去dp[stones.length - 1][target]，得到最小的剩余重量。
总结
这段代码通过动态规划解决了“最后一块石头的重量 II”的问题。它将石头分成两堆，使得两堆的重量差最小，从而得到最小的剩余重量。
494. 目标和
给你一个非负整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 ‘+’ 或 ‘-’ ，然后串联起所有整数，可以构造一个 表达式 ：
例如，nums = [2, 1] ，可以在 2 之前添加 ‘+’ ，在 1 之前添加 ‘-’ ，然后串联起来得到表达式 “+2-1” 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
示例 1：
输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3
示例 2：
输入：nums = [1], target = 1
输出：1
方法一：
class Solution {
public int findTargetSumWays(int[] nums, int target) {
int sum = 0;
for (int i = 0; i < nums.length; i++) sum += nums[i];
//如果target的绝对值大于sum，那么是没有方案的
if (Math.abs(target) > sum) return 0;
//如果(target+sum)除以2的余数不为0，也是没有方案的
if ((target + sum) % 2 == 1) return 0;
int bagSize = (target + sum) / 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];
}
}
这段代码实现了一个解决“目标和”问题的算法。题目要求是找到一种加减运算，使得数组中的元素的和等于目标值 target。这是一个变形的背包问题，下面是对代码的详细解释：
题目描述
给定一个整数数组 nums 和一个整数 target，求在数组中添加 + 或 - 符号，使得计算结果等于 target 的方法数。
解决思路
将数组划分为两个子集，使得一个子集的和减去另一个子集的和等于目标值 target。设这两个子集分别为 P 和 N。那么有以下关系：
[ P - N = \text{target} ]
[ P + N = \text{sum} ]
通过这两个方程可以得到：
[ 2P = \text{target} + \text{sum} ]
因此，问题转换为在数组中找到一个子集 P，使得 P 的和等于 (target + sum) / 2。
代码解释
计算数组总和
sumint sum = 0; for (int i = 0; i < nums.length; i++) sum += nums[i];特殊情况处理
if (Math.abs(target) > sum) return 0; if ((target + sum) % 2 == 1) return 0;- 如果
target的绝对值大于sum，那么无法通过加减运算得到target。 - 如果
(target + sum)不是偶数，也无法找到一个整数子集和使得P等于(target + sum) / 2。
- 如果
计算背包容量
bagSizeint bagSize = (target + sum) / 2;初始化动态规划数组
dpint[] dp = new int[bagSize + 1]; dp[0] = 1;dp[j]表示和为j的子集数目。初始时，和为0的子集只有一个，即空集。填充动态规划数组
dpfor (int i = 0; i < nums.length; i++) { for (int j = bagSize; j >= nums[i]; j--) { dp[j] += dp[j - nums[i]]; } }- 遍历每个数字
nums[i]。 - 更新
dp数组，从后向前遍历，确保每个数字只使用一次。 dp[j] += dp[j - nums[i]]表示当前数字nums[i]可以加入和为j - nums[i]的子集，形成和为j的子集。
- 遍历每个数字
返回结果
return dp[bagSize];返回和为
bagSize的子集数目，即满足条件的方案数。
总结
这段代码通过将问题转换为背包问题，使用动态规划求解目标和问题。通过判断特殊情况、计算背包容量和填充动态规划数组，最终得到了满足条件的方案数。
方法二：二维数组
class Solution {
public int findTargetSumWays(int[] nums, int target) {
// 01背包应用之“有多少种不同的填满背包最大容量的方法“
// 易于理解的二维数组解法及详细注释
int sum = 0;
for(int i = 0; i < nums.length; i++) {
sum += nums[i];
}
// 注意nums[i] >= 0的题目条件，意味着sum也是所有nums[i]的绝对值之和
// 这里保证了sum + target一定是大于等于零的，也就是left大于等于零（毕竟我们定义left大于right）
if(sum < Math.abs(target)){
return 0;
}
// 利用二元一次方程组将left用target和sum表示出来（替换掉right组合），详见代码随想录对此题的分析
// 如果所求的left数组和为小数，则作为整数数组的nums里的任何元素自然是没有办法凑出这个小数的
if((sum + target) % 2 != 0) {
return 0;
}
int left = (sum + target) / 2;
// dp[i][j]：遍历到数组第i个数时， left为j时的能装满背包的方法总数
int[][] dp = new int[nums.length][left + 1];
// 初始化最上行（dp[0][j])，当nums[0] == j时（注意nums[0]和j都一定是大于等于零的，因此不需要判断等于-j时的情况），有唯一一种取法可取到j，dp[0][j]此时等于1
// 其他情况dp[0][j] = 0
// java整数数组默认初始值为0
if (nums[0] <= left) {
dp[0][nums[0]] = 1;
}
// 初始化最左列（dp[i][0])
// 当从nums数组的索引0到i的部分有n个0时（n > 0)，每个0可以取+/-，因此有2的n次方中可以取到j = 0的方案
// n = 0说明当前遍历到的数组部分没有0全为正数，因此只有一种方案可以取到j = 0（就是所有数都不取）
int numZeros = 0;
for(int i = 0; i < nums.length; i++) {
if(nums[i] == 0) {
numZeros++;
}
dp[i][0] = (int) Math.pow(2, numZeros);
}
// 递推公式分析：
// 当nums[i] > j时，这时候nums[i]一定不能取，所以是dp[i - 1][j]种方案数
// nums[i] <= j时，num[i]可取可不取，因此方案数是dp[i - 1][j] + dp[i - 1][j - nums[i]]
// 由递推公式可知，先遍历i或j都可
for(int i = 1; i < nums.length; i++) {
for(int j = 1; j <= left; j++) {
if(nums[i] > j) {
dp[i][j] = dp[i - 1][j];
} else {
dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]];
}
}
}
// 打印dp数组
// for(int i = 0; i < nums.length; i++) {
// for(int j = 0; j <= left; j++) {
// System.out.print(dp[i][j] + " ");
// }
// System.out.println("");
// }
return dp[nums.length - 1][left];
}
}
这段代码实现了一个解决“目标和”问题的算法，使用二维动态规划数组来计算有多少种不同的方法可以使数组中的元素加减组合得到目标值 target。下面是对代码的详细解释：
题目描述
给定一个整数数组 nums 和一个整数 target，求在数组中添加 + 或 - 符号，使得计算结果等于 target 的方法数。
解决思路
通过将问题转换为背包问题，找到一种加减运算，使得数组中的元素的和等于目标值 target。具体来说，将数组划分为两个子集，使得一个子集的和减去另一个子集的和等于目标值 target。这可以通过以下关系来实现：
[ P - N = \text{target} ]
[ P + N = \text{sum} ]
通过这两个方程可以得到：
[ 2P = \text{target} + \text{sum} ]
因此，问题转换为在数组中找到一个子集 P，使得 P 的和等于 (target + sum) / 2。
代码解释
计算数组总和
sumint sum = 0; for (int i = 0; i < nums.length; i++) { sum += nums[i]; }特殊情况处理
if (sum < Math.abs(target)) { return 0; } if ((sum + target) % 2 != 0) { return 0; }- 如果
target的绝对值大于sum，那么无法通过加减运算得到target。 - 如果
(sum + target)不是偶数，也无法找到一个整数子集和使得P等于(target + sum) / 2。
- 如果
计算
leftint left = (sum + target) / 2;初始化动态规划数组
dpint[][] dp = new int[nums.length][left + 1]; if (nums[0] <= left) { dp[0][nums[0]] = 1; }dp[i][j]表示遍历到数组第i个数时，和为j的方法总数。初始化最左列
dp[i][0]int numZeros = 0; for (int i = 0; i < nums.length; i++) { if (nums[i] == 0) { numZeros++; } dp[i][0] = (int) Math.pow(2, numZeros); }- 初始化最左列，当和为
0时，如果数组中有n个0，则有2^n种方案，因为每个0可以取+或-。
- 初始化最左列，当和为
填充动态规划数组
dpfor (int i = 1; i < nums.length; i++) { for (int j = 1; j <= left; j++) { if (nums[i] > j) { dp[i][j] = dp[i - 1][j]; } else { dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]]; } } }- 遍历每个数字
nums[i]和每个可能的背包容量j。 - 如果
nums[i] > j，则当前数字不能放入背包，方案数为dp[i - 1][j]。 - 否则，方案数为
dp[i - 1][j] + dp[i - 1][j - nums[i]]，即不放入当前数字的方案数加上放入当前数字的方案数。
- 遍历每个数字
返回结果
return dp[nums.length - 1][left];返回和为
left的方法数，即满足条件的方案数。
总结
这段代码通过将问题转换为背包问题，使用二维动态规划数组来求解目标和问题。通过初始化和填充动态规划数组，最终得到了满足条件的方案数。
474. 一和零
给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。
如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。
示例 1：
输入：strs = [“10”, “0001”, “111001”, “1”, “0”], m = 5, n = 3
输出：4
解释：最多有 5 个 0 和 3 个 1 的最大子集是 {“10”,“0001”,“1”,“0”} ，因此答案是 4 。
其他满足题意但较小的子集包括 {“0001”,“1”} 和 {“10”,“1”,“0”} 。{“111001”} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。
示例 2：
输入：strs = [“10”, “0”, “1”], m = 1, n = 1
输出：2
解释：最大的子集是 {“0”, “1”} ，所以答案是 2 。
class Solution {
public int findMaxForm(String[] strs, int m, int n) {
//dp[i][j]表示i个0和j个1时的最大子集
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];
}
}
这段代码实现了一个解决“01背包”问题的算法，具体是关于求最大子集的问题。题目要求给定一个包含仅由 '0' 和 '1' 组成的字符串数组 strs，以及两个整数 m 和 n，要求找出数组中的最大子集，该子集中的 '0' 的数量不超过 m，且 '1' 的数量不超过 n。
解决思路
这是一个典型的二维“01背包”问题。每个字符串可以看作是一个物品，字符串中 '0' 的数量和 '1' 的数量分别对应物品的重量。目标是选择尽可能多的字符串，使得总的 '0' 和 '1' 的数量不超过 m 和 n。
代码解释
初始化动态规划数组
dpint[][] dp = new int[m + 1][n + 1];dp[i][j]表示在最多有i个'0'和j个'1'的情况下，可以组成的最大子集的大小。遍历每个字符串
strint oneNum, zeroNum; for (String str : strs) { oneNum = 0; zeroNum = 0; for (char ch : str.toCharArray()) { if (ch == '0') { zeroNum++; } else { oneNum++; } }- 统计字符串中
'0'和'1'的数量。 oneNum表示字符串中'1'的数量。zeroNum表示字符串中'0'的数量。
- 统计字符串中
更新动态规划数组
dpfor (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); } }- 通过倒序遍历来确保每个字符串只被计算一次。
- 对于每个
dp[i][j]，考虑当前字符串是否放入背包：- 如果不放入，
dp[i][j]保持不变。 - 如果放入，新的状态是
dp[i - zeroNum][j - oneNum] + 1。 - 取两者的最大值更新
dp[i][j]。
- 如果不放入，
返回结果
return dp[m][n];最后，
dp[m][n]即为最多有m个'0'和n个'1'的情况下，可以组成的最大子集的大小。
总结
这段代码通过动态规划解决了“01背包”问题。使用二维数组 dp 来存储在不同的 '0' 和 '1' 限制下可以组成的最大子集的大小。通过遍历每个字符串，计算其 '0' 和 '1' 的数量，并更新 dp 数组，最终得到满足条件的最大子集大小。