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 <= 30
• 1 <= stones[i] <= 100

class Solution {
public:int lastStoneWeightII(vector<int>& stones) {vector<int> dp(150001,0);int sum = 0;for(int i=0;i<stones.size();i++){sum+=stones[i];}int target = sum/2;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];}
};

解題思路：

問題背景

問題描述：有一堆石頭，每次從中挑選兩塊石頭碰撞，碰撞后會得到一塊新石頭（重量為兩塊石頭的差值），直到只剩下一塊石頭或沒有石頭。求最后可能剩下的最小石頭重量。

核心思路轉化

這個問題可以轉化為：

• 將石頭分成兩堆，使兩堆的重量盡可能接近
• 兩堆重量的差值就是最后可能剩下的最小重量

這是因為每次碰撞相當于從總重量中減去 twice of 較小的那塊石頭的重量，最優策略是讓兩堆石頭重量盡可能接近。

代碼原理詳解

1. 動態規劃數組定義：
   dp[j]表示能從石頭中選出若干塊，使得它們的總重量最大為j

2. 計算目標值：
   sum是所有石頭的總重量
   target是sum/2，我們嘗試找到不超過這個值的最大子集和

3. 0-1 背包問題求解：

   • 外層循環遍歷每塊石頭（物品）
   • 內層循環從target往當前石頭重量遍歷（0-1 背包的典型做法，避免重復使用同一物品）
   • dp[j] = max(dp[j], dp[j - stones[i]] + stones[i])表示對于重量j，要么不選當前石頭保持dp[j]，要么選當前石頭得到dp[j - stones[i]] + stones[i]

4. 計算結果：
   sum - dp[target] - dp[target]表示總重量減去兩倍的最大子集和（即兩堆石頭的重量差）

這個解法的時間復雜度是 O (n×target)，空間復雜度是 O (target)，其中 n 是石頭數量，target 是總重量的一半。

494. 目標和

class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {int sum = 0;for (int i = 0; i < nums.size(); i++) sum += nums[i];if (abs(target) > sum) return 0; // 此時沒有方案if ((target + sum) % 2 == 1) return 0; // 此時沒有方案int bagSize = (target + sum) / 2;vector<int> dp(bagSize + 1, 0);dp[0] = 1;for(int i=0;i<nums.size();i++){for(int j = bagSize;j>=nums[i];j--){dp[j] += dp[j-nums[i]];}}return dp[bagSize];}
};

給每個數字添加+或-，本質上是將數組分成兩組：

• 一組數字前面加+（和為left）
• 另一組數字前面加-（和為right）

根據題意，我們有：

plaintext

left - right = target  // 表達式結果等于target
left + right = sum     // 所有數字的總和

將兩式相加可得：2*left = target + sum，即?left = (target + sum) / 2

因此問題轉化為：找到有多少種方法可以從數組中選出一些數字，使它們的和等于 left

代碼解析

1. 邊界條件判斷：

   if (abs(target) > sum) return 0; // 目標值的絕對值大于總和，不可能實現
   if ((target + sum) % 2 == 1) return 0; // 和為奇數，無法被2整除，沒有方案
   

2. 計算背包大小：

   int bagSize = (target + sum) / 2;
   

   ?

   這里的bagSize就是我們要找的left值，即需要選出和為bagSize的數字組合

3. 動態規劃初始化：

   ?

   vector<int> dp(bagSize + 1, 0);
   dp[0] = 1; // 表示湊出和為0的方法有1種（什么都不選）
   

   ?

   dp[j]的含義是：有多少種方法可以選出和為 j 的數字組合

4. 填充 DP 數組：

   ?

   for (int i = 0; i < nums.size(); i++) { // 遍歷每個數字for (int j = bagSize; j >= nums[i]; j--) { // 倒序遍歷背包dp[j] += dp[j - nums[i]];}
   }
   

   ?
   • 對于每個數字，我們可以選擇 "放入背包"（即該數字前面加+）或 "不放入背包"（即該數字前面加-）
   • 狀態轉移方程dp[j] += dp[j - nums[i]]表示：湊出和為 j 的方法數 = 不選當前數字的方法數 + 選當前數字的方法數（此時需要加上湊出 j-nums [i] 的方法數）
   • 倒序遍歷是為了保證每個數字只被使用一次（0-1 背包特性）

5. 返回結果：

   return dp[bagSize];
   

   ?

   dp[bagSize]就是能湊出和為bagSize的方法總數，也就是我們要求的答案

示例說明

以nums = [1,1,1,1,1]，target = 3為例：

• 總和sum = 5
• bagSize = (3 + 5) / 2 = 4
• 問題轉化為：有多少種方法從數組中選出和為 4 的數字
• 答案是 5 種，對應 5 種不同的表達式

474. 一和零

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

問題理解

給定一組二進制字符串，每個字符串包含0和1。我們需要選擇一些字符串，使得：

• 所有選中字符串中0的總數不超過?m

• 所有選中字符串中1的總數不超過?n

• 選中的字符串數量盡可能多

動態規劃思路

1. 狀態定義

dp[i][j]?表示：使用最多?i?個0和?j?個1時，能夠組成的最大字符串數量

2. 狀態轉移

對于每個字符串，我們有兩種選擇：

• 不選這個字符串：dp[i][j]?保持不變

• 選這個字符串：dp[i][j] = dp[i - zeros][j - ones] + 1

狀態轉移方程：

cpp

dp[i][j] = max(dp[i][j], dp[i - zeros][j - ones] + 1);

3. 為什么從后往前遍歷？

這是0-1背包問題的核心技巧：

• 從后往前遍歷：確保每個字符串只被使用一次（避免重復選擇）

• 如果從前往后遍歷，會變成完全背包問題（每個物品可以選多次）

4. 具體步驟

1. 初始化：創建?(m+1) × (n+1)?的二維數組，初始值為0

2. 遍歷每個字符串：

   • 計算當前字符串的0和1的數量

   • 從?m?到?zeros，從?n?到?ones?反向更新dp表

3. 返回結果：dp[m][n]?就是最大數量

示例說明

假設?strs = ["10", "0001", "111001", "1", "0"],?m = 5,?n = 3

對于字符串 "10"：

• zeros = 1, ones = 1

• 更新所有?i >= 1?且?j >= 1?的位置

對于字符串 "0001"：

• zeros = 3, ones = 1

• 更新所有?i >= 3?且?j >= 1?的位置

以此類推...

時間復雜度

• 外層循環：O(S)，S為字符串數量

• 內層循環：O(M × N)

• 總復雜度：O(S × M × N)

空間復雜度

• O(M × N)，即dp表的大小

這種解法巧妙地利用了動態規劃和背包問題的思想，通過反向遍歷確保每個字符串只被考慮一次，從而找到最優解。