思路：

动态规划

1. 总体上来说，就是找两块最接近的石头碰撞，拓展出来，就是找两组最接近的石头碰撞。——就是找两个和最接近的子集。
2. 到这里就和上一题《416. 分割等和子集》差不多了。
3. 因为sum/2是向下取整，所以half肯定是<=sum的半值的。
4. 就算sum是偶数，half恰好是sum的一半，也不能保证刚好就有石头能累加和得到half。因为碰撞完剩余的石头不一定是0。所以我们求的dp[half]肯定是小于等于half的。
5. 所以我们求的dp[half]，是重量小的那一组。剩余的半组石头是重量大的sum-dp[half]。将二者碰撞，相减，就得到答案。

对这个过程不理解的话，一定要把sum，half，dp[]数组的全过程，给打印出来，看懂。

class Solution {public int lastStoneWeightII(int[] stones) {int n = stones.length;// 使用stream快速求和int sum = Arrays.stream(stones).sum();int half = sum / 2;// // 检查sum和half数值// System.out.println("sum = " + sum);// System.out.println("half = " + half);// 背包的容量是halfint[] dp = new int[half + 1];// 遍历for (int i = 0; i < n; i++) {// 倒序遍历for (int j = half; j >= stones[i]; j--) {dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);}// // 遍历检查dp[]数组// for (int j = 0; j <= half; j++) {//     System.out.print(dp[j] + " ");// }// System.out.println(" ");}return sum - dp[half] - dp[half];}
}

简洁版代码：

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

方法：回溯

思路：

class Solution {int count = 0;public int findTargetSumWays(int[] nums, int target) {backtracking(nums, target, 0, 0);return count;}public void backtracking(int[] nums, int target, int index, int sum) {if (index == nums.length) {if (sum == target) {count++;}} else {backtracking(nums, target, index + 1, sum + nums[index]);backtracking(nums, target, index + 1, sum - nums[index]);}}
}

方法：动态规划

思路：

题目分析：

假设要加’+‘号的元素有pos个，要加’-'的元素设为neg，就是sum-pos个

因为pos - neg = target，等同于pos - (sum-pos) = target

可以得出 pos = (sum + target) / 2

此时我们可以求，最多有多少种方法，可以装满容量为pos的背包

动态规划分析：

1. 确定dp[j]的含义：有dp[j]种方法填满容量为j的包
2. 确定递推公式：
   1. 情况一：不放nums[i]，就直接是“上一层”的dp[j]，以为这是滚动数组，所以直接等于
   2. 情况二：放num[i]，就看上一层[j - nums[i]]的位置有多少种方法（因为这里不是求最大值，所以不用+value[i]）
   3. 因为这里求的是“最多有多少种方法”，所以并不是取max，而是把情况一和情况二求和
   4. 公式：dp[j] = dp[j] + dp[j - nums[i]];
3. 初始化，dp[0] = 1。

class Solution {public int findTargetSumWays(int[] nums, int target) {int sum = Arrays.stream(nums).sum();//如果target的绝对值大于sum，那么是没有方案的if (Math.abs(target) > sum) {return 0;}//如果(target+sum)除以2的余数不为0，也是没有方案的if ((target + sum) % 2 == 1) {return 0;}int pos = (target + sum) / 2;int[] dp = new int[pos + 1];dp[0] = 1;for (int i = 0; i < nums.length; i++) {for (int j = pos; j >= nums[i]; j--) {// 情况一：不放nums[i]，就直接是“上一层”的dp[j]，以为这是滚动数组，所以直接等于// 情况二：放num[i]，就看上一层[j - nums[i]]的位置有多少种方法（因为这里不是求最大值，所以不用+value[i]）// 因为这里求的是“最多有多少种方法”，所以并不是取max，而是把情况一和情况二求和dp[j] = dp[j] + dp[j - nums[i]];}// // 遍历检查dp[]数组// for (int j = 0; j <= pos; j++) {//     System.out.print(dp[j] + " ");// }// System.out.println(" ");}return dp[pos];}
}

简洁版代码：

class Solution {public int findTargetSumWays(int[] nums, int target) {int sum = Arrays.stream(nums).sum();if (Math.abs(target) > sum) {return 0;}if ((target + sum) % 2 == 1) {return 0;}int pos = (target + sum) / 2;int[] dp = new int[pos + 1];dp[0] = 1;for (int i = 0; i < nums.length; i++) {for (int j = pos; j >= nums[i]; j--) {dp[j] = dp[j] + dp[j - nums[i]];}}return dp[pos];}
}

思路：

注意本题虽然是二维数组，但是依然是滚动数组。因为维度多了一个，要记录0和1的情况。

1. dp数组定义：dp[i][j]表示i个0和j个1时的最大子集
2. dp递推公式：dp[i][j] = Math.max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
3. 初始化：全部为0就可以
4. 递归顺序：因为是滚动数组，i和j都要倒序遍历

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);}}// // 遍历检查dp[]数组// for (int i = 0; i <= m; i++) {//     for (int j = 0; j <= n; j++) {//         System.out.print(dp[i][j] + " ");//     }//     System.out.print(" ");// }}return dp[m][n];}
}

这题增加多了一个维度之后，更加烧脑了。建议把dp数组打印出来，自己对着代码推一遍。加深了理解。