思路：

動態規劃

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數組打印出來，自己對著代碼推一遍。加深了理解。