分割等和子集
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/partition-equal-subset-sum
问题叙述
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
示例 1：
输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。
示例 2：
输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。
提示：
1 <= nums.length <= 200
1 <= nums[i] <= 100
分析
经典的01背包问题，要使得两个子集的元素和相等，那么首先子集的元素和必须为偶数才有可能.
所以我们先求出数组元素的总和，如果是奇数就直接返回false。如果是偶数，那我们就转化为容量大小为sum/2的背包
于是就可以创建一个二维数组dp[nums.length][sum / 2 + 1];
dp[i][j]表示：容量为j的背包，从前i个元素中任取，能获得的最大元素和
每个元素只有两种状态：取与不取。
- 如果我们不取该元素的话，那么状态转移方程为：dp[i][j] = dp[i-1][j];
- 如果我们取该元素的话，那我们必须事先留出该元素所需要的的空间，那么就是在背包容量为j-nums[i]的条件下，加上该元素。对应的状态转移方程为：dp[i][j] = dp[i-1][j-nums[i]] + nums[i];
最终我们的dp[i][j]就是在上述两种情况中，选取最大值
所以最终的状态转移方程为：dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - nums[i]] + nums[i]);
绝大多数的二维dp可以优化成一维dp。
注意到状态转移方程只与容量为j-nums[i]的背包有关，放在二维网格里，就是与其左上方的某个格子有关。
所以我们把dp数组降成一维的时候，必须从后往前遍历，这样才能保证dp[j]先比dp[j-nums[i]]变化。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public boolean canPartition(int[] nums) {
int sum = 0;
for (int n : nums) sum += n;
if (sum % 2 == 1) return false;
int target = sum / 2;
int[][] dp = new int[nums.length][target + 1];
for (int j = 0; j <= target; j++) {
if (j >= nums[0]) dp[0][j] = nums[0];
}
for (int i = 1; i < nums.length; i++) {
for (int j = 1; j <= target; j++) {
if (j >= nums[i]) dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - nums[i]] + nums[i]);
else dp[i][j] = dp[i-1][j];
}
}
return dp[nums.length - 1][target] == target;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public boolean canPartition(int[] nums) {
int sum = 0;
for (int n : nums) sum += n;
if (sum % 2 != 0) return false;
int target = sum / 2;
int[] dp = new int[target + 1];
for (int num : nums)
for (int j = target; j >= 0; j--) {
if(j >= num) dp[j] = Math.max(dp[j], dp[j - num] + num);
}
return dp[target] == target;
}
}
|
最后一块石头的重量II
问题叙述
分析
跟上题一样，依旧是把石头尽可能平均的分为两堆，这样就能保证剩下的最后一块石头质量最小
还是先求出石头的总质量Sum，把石头平均分为A，B两堆，target = Sum/2，由于整型除法会自动向下取整
所以A堆石头重target，B堆石头重Sum-target，B一定是大于A的，所以B-A=Sum-2*target就是结果
依旧是创建一个二维数组dp[stones.length][target+1];
dp[i][j]表示从前i个元素中任取，能使容量为j的背包，装下的最大质量
每块石头只有两种状态，取与不取
- 如果不取，那就要保持上一个状态dp[i][j] = dp[i - 1][j];
- 如果取，就要预留空间，dp[i][j] = dp[i - 1][j-stones[i]] + stones[i];
最终的dp[i][j]就是从上述两种状态中选取最大情况，dp[i][j] = Math.max(dp[i-1][j], dp[i - 1][j - stones[i]] + stones[i]);
降为一维DP的方法与上题一致
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public int lastStoneWeightII(int[] stones) {
int sum = 0;
for (int stone : stones) sum += stone;
int target = sum / 2;
int[][] dp = new int[stones.length][target + 1];
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][j] = Math.max(dp[i - 1][j], dp[i - 1][j - stones[i]] + stones[i]);
else dp[i][j] = dp[i - 1][j];
}
}
return sum - 2 * dp[stones.length - 1][target];
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public int lastStoneWeightII(int[] stones) {
int sum = 0;
for (int stone : stones) sum += stone;
int target = sum / 2;
int[] dp = new int[target + 1];
for (int stone : stones)
for (int j = target; j >= 0; j--)
if (j >= stone) dp[j] = Math.max(dp[j], dp[j - stone] + stone);
return sum - 2 * dp[target];
}
}
|
目标和
问题叙述
分析
Code
这次就不写二维DP了，以后能用一维DP就用一维的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public int findTargetSumWays(int[] nums, int target) {
int sum = 0;
for (int num : nums) sum += num;
if ((sum + target) % 2 == 1 || Math.abs(target) > sum) return 0;
int size = (sum + target) / 2;
int[] dp = new int[size + 1];
dp[0] = 1;
for (int num : nums) {
for (int j = size; j >= num; j--) {
dp[j] += dp[j - num];
}
}
return dp[size];
}
}
|
