一、LeetCode1049. 最后一塊石頭的重量 II
題目鏈接：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
提示：
1 <= stones.length <= 301 <= stones[i] <= 100
算法分析：
定義dp數組及下標含義：
dp[j]:表示容量為j的背包所能裝的物品最大價值（石頭的重量）為dp[j]。
遞推公式：
dp[j]=max(dp[j],dp[j-stones[i]]+stones[i])。
初始化：
dp[0]=0。
遍歷順序：
先遍歷物品在遍歷背包容量。
代碼如下：
class Solution {public int lastStoneWeightII(int[] stones) {int len = stones.length;int sum = 0;for(int i = 0; i < len; i++)sum += stones[i];int mid;mid = sum / 2;int[] dp = new int[mid + 1];for(int i = stones[0]; i <= mid; i++)dp[i] = stones[0];for(int i = 1; i < len; i++) {for(int j = mid; j >= stones[i]; j--) {dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);}}return sum - dp[mid] * 2;}
}二、LeetCode494. 目標和
題目鏈接：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
提示：
1 <= nums.length <= 200 <= nums[i] <= 10000 <= sum(nums[i]) <= 1000-1000 <= target <= 1000
算法分析：
設添加+的元素集合總和為add，添加-的元素集合總和為des，則原數組的所有元素之和sum=add+des
由題意target=add-des；
des=add-target;
sum=add+(add-target);
add=(sum+target)/2;
所以我們只需要在原數組中找出和等于add的方法數就可以了。
于是我們可以用動態規劃中背包思路來解。
定義dp數組及下標含義：
dp[j]表示元素和為j的方法有dp[j]種。
遞推公式：
dp[j]+=dp[j-nums[i]]；
例如：若有元素1，2，3，4，5，6,則加上該元素后和為5的方法有dp[5]=dp[5-1]+dp[5-2]+dp[5-3]+dp[5-4]+dp[5-5]種(j>=nums[i])。
初始化：
我們初始化dp[0]=1;
表示元素和為0的方法有一種，因為如果為0的話那么所有的遞推結果都將為0。
遍歷順序：
先遍歷元素在遍歷總和。
代碼如下：
class Solution {public int findTargetSumWays(int[] nums, int target) {int len = nums.length;int sum = 0;//數組總和for(int i = 0; i < len; i++)sum += nums[i];if(Math.abs(target) > sum) return 0;//如果target的絕對值大于sum，那么無論數組中所有元素都取正還是負都不肯能等于targetif((sum + target) % 2 != 0) return 0;//沒有結果，如sum是5target是0的話，無解int add = (sum + target) / 2;int[] dp = new int[add + 1];dp[0] = 1;for(int i = 0; i < len; i++) {for(int j = add; j >= nums[i]; j--) {dp[j] += dp[j - nums[i]];}}return dp[add];}
}總結
求背包問題時要明確定義dp數組所表示的含義，對于不同的問題可能會有不同的定義，
如1049. 最后一塊石頭的重量 II中，dp[j]表示容量為j的背包所能裝的石頭的重量最大為dp[j]。
而494. 目標和中dp[j]表示裝滿容量為j的方法有dp[j]種。
