分割等和子集
给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
注意:
- 每个数组中的元素不会超过 100
- 数组的大小不会超过 200
示例 1:
输入: [1, 5, 11, 5]
输出: true
解释: 数组可以分割成 [1, 5, 5] 和 [11].
示例 2:
输入: [1, 2, 3, 5]
输出: false
解释: 数组不能分割成两个元素和相等的子集
方法一：DFS
我的方法（超时）
public boolean canPartition(int[] nums) {
int sum = 0;
for (int num : nums) {
sum += num;
}
if (sum % 2 != 0) {
return false;
}
return dfs(nums, 0, 0, sum / 2);
}
public boolean dfs(int[] nums, int i, int partSum, int sum) {
if (partSum == sum) {
return true;
}
if (partSum > sum || i == nums.length) {
return false;
}
return dfs(nums, i + 1, partSum + nums[i], sum) || dfs(nums, i + 1, partSum, sum);
}
改进：将数组排序，先考虑较大的元素，这样好剪枝
public boolean canPartition(int[] nums) {
int sum = 0;
Arrays.sort(nums);
for (int num : nums) {
sum += num;
}
if (sum % 2 != 0) {
return false;
}
return dfs(nums, nums.length - 1, 0, sum / 2);
}
public boolean dfs(int[] nums, int i, int partSum, int sum) {
if (partSum == sum) {
return true;
}
if (partSum > sum || i < 0 || nums[i] > sum) {
return false;
}
return dfs(nums, i - 1, partSum + nums[i], sum) || dfs(nums, i - 1, partSum, sum);
}
方法二：动态规划
其实是背包问题
dp[i][j]表示从nums[0]到nums[i]中挑一些数，每个数最多用一次，能否使和为j
public boolean canPartition(int[] nums) {
int sum = 0;
for (int num : nums) {
sum += num;
}
if (sum % 2 != 0) {
return false;
}
sum /= 2;
boolean[][] dp = new boolean[nums.length][sum + 1];
if (nums[0] <= sum) {
//只考虑第一个数时，只有和为第一个数才为true
dp[0][nums[0]] = true;
}
for (int i = 1; i < nums.length; i++) {
for (int j = 0; j <= sum; j++) {
dp[i][j] = dp[i - 1][j];//不选择第nums[i]
if (j - nums[i] >= 0) {
//dp[i - 1][j - nums[i]]选择num[i]
dp[i][j] = dp[i][j] || dp[i - 1][j - nums[i]];
}
}
}
return dp[nums.length - 1][sum];
}
空间优化：
填表的时候只用到了上一行，所以可压缩为一维数组
public boolean canPartition(int[] nums) {
int sum = 0;
for (int num : nums) {
sum += num;
}
if (sum % 2 != 0) {
return false;
}
sum /= 2;
boolean[] dp = new boolean[sum + 1];
if (nums[0] <= sum) {
dp[nums[0]] = true;
}
for (int i = 1; i < nums.length; i++) {
//由于填表时用到了正上方和左上方的元素，为避免新的值覆盖了原有的值，所以从后往前遍历
for (int j = sum; j >= 0; j--) {
if (j - nums[i] >= 0) {
dp[j] = dp[j] || dp[j - nums[i]];
}
}
}
return dp[sum];
}
最后一块石头的重量
有一堆石头，每块石头的重量都是正整数。
每一回合，从中选出两块** 最重的** 石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
- 如果
x == y，那么两块石头都会被完全粉碎； - 如果
x != y，那么重量为x的石头将会完全粉碎，而重量为y的石头新重量为y-x。
最后，最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下，就返回0。
示例：
输入：[2,7,4,1,8,1]
输出：1
解释：
先选出 7 和 8，得到 1，所以数组转换为 [2,4,1,1,1]，
再选出 2 和 4，得到 2，所以数组转换为 [2,1,1,1]，
接着是 2 和 1，得到 1，所以数组转换为 [1,1,1]，
最后选出 1 和 1，得到 0，最终数组转换为 [1]，这就是最后剩下那块石头的重量。
大根堆
public int lastStoneWeight(int[] stones) {
Queue<Integer> queue = new PriorityQueue<>((o1, o2) -> o2-o1);
for (int num : stones) {
queue.add(num);
}
while (queue.size() > 1) {
int num1 = queue.poll();
int num2 = queue.poll();
if (num1 != num2) {
queue.add(num1 - num2);
}
}
return queue.isEmpty() ? 0 : queue.poll();
}
最后一块石头的重量 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]，这就是最优值。
和等和分割子集类似
把问题转化成将石头分成两堆，使两堆差值最小，理想情况两堆重量一样，总之使每堆总重量约接近sum/2，即背包容量为sum/2
public int lastStoneWeightII(int[] stones) {
int sum = Arrays.stream(stones).sum();
int n = stones.length, m = sum / 2;
// n + 1 避免处理i=0
boolean[][] dp = new boolean[n + 1][m + 1];
dp[0][0] = true;
for (int i = 0; i < n; i++) {
for (int j = 0; j <= m; j++) {
if (j - stones[i] >= 0) {
dp[i + 1][j] = dp[i][j] || dp[i][j - stones[i]];
} else {
dp[i + 1][j] = dp[i][j];
}
}
}
for (int i = m; i >= 0; i--) {
// 抵消掉能放进背包的重量
if (dp[n][i]) {
return sum - 2 * i;
}
}
// 不可能
return -1;
}
目标和
给你一个整数数组 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
方法一：回溯
private int res;
public int findTargetSumWays(int[] nums, int target) {
dfs(nums, 0, target);
return res;
}
private void dfs(int[] nums, int i, int target) {
if (i == nums.length) {
if (target == 0) {
res++;
}
return;
}
dfs(nums, i + 1, target - nums[i]);
dfs(nums, i + 1, target + nums[i]);
}
方法二：动态规划
个数字都有两种状态：被进行“+”， 或者被进行“-”，因此可以将数组分成A和B两个部分：
A部分的数字全部进行“+”操作，B部分的数字全部进行“-”操作。
设数组的和为sum，A部分的和为sumA，B部分的和为sumB
根据上面的分析，我们可以得出： sumA + sumB = sum (1)
同时有： sumA - sumB = target (2)
将(1)式与(2)式相加，可以得到： 2sumA = sum + target (3)
即：sumA = (sum + target) / 2 ，自此，原问题可以转化为0-1背包问题：
有一些物品，第i个物品的重量为nums[i]， 背包的容量为sumA，问：有多少种方式将背包【恰好填满】
这里需要注意的是，由于每个数字都是非负整数，因此sumA, sumB, sum都是非负整数。
根据(3)， 2sumA一定为偶数(自然数的性质，2n是偶数)，因此sum + target也应该是偶数。如果计算出的sum + target不是偶数，则与推导过程矛盾，本题无解。
public int findTargetSumWays(int[] nums, int target) {
int sum = Arrays.stream(nums).sum();
if ((sum + target) % 2 != 0 || Math.abs(target) > sum) {
return 0;
}
int n = nums.length, m = (sum + target) / 2;
int[][] dp = new int[n + 1][m + 1];
dp[0][0] = 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j <= m; j++) {
dp[i + 1][j] = dp[i][j];
if (j - nums[i] >= 0) {
dp[i + 1][j] += dp[i][j - nums[i]];
}
}
}
return dp[n][m];
}
空间优化：
public int findTargetSumWays(int[] nums, int target) {
int sum = Arrays.stream(nums).sum();
if ((sum + target) % 2 != 0 || Math.abs(target) > sum) {
return 0;
}
int n = nums.length, m = (sum + target) / 2;
int[] dp = new int[m + 1];
dp[0] = 1;
for (int i = 0; i < n; i++) {
for (int j = m; j >= 0; j--) {
if (j - nums[i] >= 0) {
dp[j] += dp[j - nums[i]];
}
}
}
return dp[m];
}
一和零
给你一个二进制字符串数组 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 。
动态规划
把总共的 0 和 1 的个数视为背包的容量，每一个字符串视为装进背包的物品。这道题就可以使用 0-1 背包问题的思路完成，这里的目标值是能放进背包的字符串的数量。
动态规划的思路是：物品一个一个尝试，容量一点一点尝试，每个物品分类讨论的标准是：选与不选。
定义状态：尝试题目问啥，就把啥定义成状态。dp[i][j][k] 表示输入字符串在子区间 [0, i] 能够使用 j 个 0 和 k 个 1 的字符串的最大数量。
public int findMaxForm(String[] strs, int m, int n) {
int len = strs.length;
int[][][] dp = new int[len + 1][m + 1][n + 1];
for (int i = 0; i < len; i++) {
int[] count = count(strs[i]);
for (int j = 0; j <= m; j++) {
for (int k = 0; k <= n; k++) {
if (j - count[0] >= 0 && k - count[1] >= 0) {
dp[i + 1][j][k] = Math.max(dp[i][j][k], dp[i][j - count[0]][k - count[1]] + 1);
} else {
dp[i + 1][j][k] = dp[i][j][k];
}
}
}
}
return dp[len][m][n];
}
private int[] count(String s) {
int[] res = new int[2];
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '0') {
res[0]++;
} else {
res[1]++;
}
}
return res;
}
空间优化：
public int findMaxForm(String[] strs, int m, int n) {
int len = strs.length;
int[][] dp = new int[m + 1][n + 1];
for (int i = 0; i < len; i++) {
int[] count = count(strs[i]);
for (int j = m; j >= 0; j--) {
for (int k = n; k >= 0; k--) {
if (j - count[0] >= 0 && k - count[1] >= 0) {
dp[j][k] = Math.max(dp[j][k], dp[j - count[0]][k - count[1]] + 1);
}
}
}
}
return dp[m][n];
}
private int[] count(String s) {
int[] res = new int[2];
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '0') {
res[0]++;
} else {
res[1]++;
}
}
return res;
}
