有一堆石頭，用整數(shù)數(shù)組 stones 表示。其中 stones[i] 表示第 i 塊石頭的重量。

每一回合，從中選出任意兩塊石頭，然后將它們一起粉碎。假設(shè)石頭的重量分別為 x 和 y，且 x <= y。那么粉碎的可能結(jié)果如下：

• 如果 x == y，那么兩塊石頭都會被完全粉碎；
• 如果 x != y，那么重量為 x 的石頭將會完全粉碎，而重量為 y 的石頭新重量為 y-x。

最后，最多只會剩下一塊 石頭。返回此石頭 最小的可能重量 。如果沒有石頭剩下，就返回 0。

示例 1：

輸入：stones = [2,7,4,1,8,1]
輸出：1
解釋：
組合 2 和 4，得到 2，所以數(shù)組轉(zhuǎn)化為 [2,7,1,8,1]，
組合 7 和 8，得到 1，所以數(shù)組轉(zhuǎn)化為 [2,1,1,1]，
組合 2 和 1，得到 1，所以數(shù)組轉(zhuǎn)化為 [1,1,1]，
組合 1 和 1，得到 0，所以數(shù)組轉(zhuǎn)化為 [1]，這就是最優(yōu)值。

示例 2：

輸入：stones = [31,26,33,21,40]
輸出：5

提示：

• 1 <= stones.length <= 30
• 1 <= stones[i] <= 100

給你一個整數(shù)數(shù)組 nums 和一個整數(shù) target 。

向數(shù)組中的每個整數(shù)前添加 '+' 或 '-' ，然后串聯(lián)起所有整數(shù)，可以構(gòu)造一個 表達(dá)式 ：

• 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串聯(lián)起來得到表達(dá)式 "+2-1" 。

返回可以通過上述方法構(gòu)造的、運(yùn)算結(jié)果等于 target 的不同 表達(dá)式 的數(shù)目。

示例 1：

輸入：nums = [1,1,1,1,1], target = 3
輸出：5
解釋：一共有 5 種方法讓最終目標(biāo)和為 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

給你一個二進(jìn)制字符串?dāng)?shù)組 strs 和兩個整數(shù) 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"} 不滿足題意，因?yàn)樗?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

1. 確定dp數(shù)組以及下標(biāo)的定義
   dp[i][j]：最多有i個0和j個1的str的最大子集的大小dp[i][j]。

2. 遞推公式
   dp[i][j] 可以由前一個strs里的字符串推導(dǎo)出來，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);

   此時大家可以回想一下01背包的遞推公式：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

3. 初始化
   因?yàn)槲锲穬r值不會是負(fù)數(shù)，初始為0，保證遞推的時候dp[i][j]不會被初始值覆蓋。

4. 遍歷順序
   for循環(huán)遍歷物品，內(nèi)層for循環(huán)遍歷背包容量且從后向前遍歷！

5. 舉例
   

class Solution {
public:int findMaxForm(vector<string>& strs, int m, int n) {vector<vector<int>> dp(m + 1, vector<int> (n + 1, 0)); // 默認(rèn)初始化0for (string str : strs) { // 遍歷物品int oneNum = 0, 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];}
};