最后一塊石頭的重量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 <= 30
• 1 <= stones[i] <= 100

本題與分割等和子集很像。

使用滾動數組,dp[j]表示容量為j的背包所具有的價值（j容量的石頭價值也是j）

初始化均為0.

?遞推公式?要么沒使用i位置的石頭 就是dp[j]；要么使用i位置的石頭 就是dp[j-stone[i]]+stone[i]。

順序，由于使用的是滾動數組，那我們就先遍歷物品，再遍歷容量，且容量遍歷是從后往前遍歷。

最后的輸出，我們得到了 dp[target], sum- dp[target]就是另一半的值，做差就可得到結果。

class Solution {
public:int lastStoneWeightII(vector<int>& stones) {int sum = 0;for (int i : stones) {sum += i;}int target = sum / 2;vector<int> dp (target+1,0);for(int i = 0;i<stones.size();i++){for(int j = target;j>=stones[i];j--){dp[j] = max(dp[j],dp[j-stones[i]]+stones[i]);}}return (sum - dp[target]) - dp[target];}
};

---

目標和

給你一個非負整數數組 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 <= 20
0 <= nums[i] <= 1000
0 <= sum(nums[i]) <= 1000
-1000 <= target <= 1000

假設加法的總和為x，那么減法對應的總和就是sum - x。

所以我們要求的是 x - (sum - x) = target

x = (target + sum) / 2

此時問題就轉化為，用nums裝滿容量為x的背包，有幾種方法。

（C++代碼中，輸入的S 就是題目描述的 target）
if ((target + sum) % 2 == 1) return 0; // 此時沒有方案

同時如果target 的絕對值已經大于sum，那么也是沒有方案的。

if (abs(target) > sum) return 0; // 此時沒有方案

確定dp數組以及下標的含義

先用 二維 dp數組求解本題，dp[i][j]：使用 下標為[0, i]的nums[i]能夠湊滿j（包括j）這么大容量的包，有dp[i][j]種方法。

遞推公式

抽象化如下：

• 不放物品i：即背包容量為j，里面不放物品i，裝滿有dp[i - 1][j]中方法。

• 放物品i： 即：先空出物品i的容量，背包容量為（j - 物品i容量），放滿背包有 dp[i - 1][j - 物品i容量] 種方法。

if(nums[i]>j) dp[i][j] = dp[i-1][j];
else dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i]]; 

初始化?

最上方 把nums[0]=j 的dp[0][j]位置的dp初始化為1.

至于最左側的初始化，要考慮nums數組中有多少個0，如果沒有0，初始化為1；如果有n個0，初始化為2的n次方。

遍歷順序任意。

class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {int sum = 0;for(int num:nums){sum += num;}if((sum+target)%2==1) return 0;if(abs(target)>sum) return 0;int bagSize = (sum+target)/2;vector<vector<int>> dp(nums.size(),vector<int>(bagSize+1,0));for(int i = 0;i<nums.size();i++){dp[i][0] = 1;}for(int j = 0;j<=bagSize;j++){if(j==nums[0]){dp[0][j] = 1;}}int numZero = 0;for (int i = 0; i < nums.size(); i++) {if (nums[i] == 0) numZero++;dp[i][0] = (int) pow(2.0, numZero);}for(int i = 1;i<nums.size();i++){for(int j = 1;j<=bagSize;j++){if(nums[i]>j) dp[i][j] = dp[i-1][j];else dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i]]; }}return dp[nums.size()-1][bagSize];}
};

?

---

一和零

給你一個二進制字符串數組?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 。

示例 2：

輸入：strs = ["10", "0", "1"], m = 1, n = 1
輸出：2
解釋：最大的子集是 {"0", "1"} ，所以答案是 2 。

提示：

• 1 <= strs.length <= 600
• 1 <= strs[i].length <= 100
• strs[i]?僅由?'0'?和?'1'?組成
• 1 <= m, n <= 100

確定dp數組（dp table）以及下標的含義

dp[i][j]：最多有i個0和j個1的strs的最大子集的大小為dp[i][j]。

確定遞推公式：

dp[i][j] 可以由前一個strs里的字符串推導出來，strs里的字符串有zeroNum個0，oneNum個1。

dp[i][j] 就可以是 dp[i - zeroNum][j - oneNum] + 1。

然后我們在遍歷的過程中，取dp[i][j]的最大值。

所以遞推公式：dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);

?順序均由后向前。

class Solution {
public:int findMaxForm(vector<string>& strs, int m, int n) {vector<vector<int>> dp(m+1,vector<int>(n+1,0));for(string str:strs){int oneNum = 0;int zeroNum = 0;for(char c:str){if(c=='0') zeroNum++;else oneNum++;}for(int i = m;i>=zeroNum;i--){for(int j = n;j>=oneNum;j--){dp[i][j] = max(dp[i][j],dp[i-zeroNum][j-oneNum]+1);}}}return dp[m][n];}
};

?