LeetCode.1049?最后一塊石頭的重量 II

題目鏈接?最后一塊石頭的重量II

題解

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 target = sum / 2;int[] dp = new int[target + 1];for(int i = 0;i<len;i++){for(int j = target;j>=stones[i];j--){dp[j] = Math.max(dp[j],dp[j-stones[i]] + stones[i]);}}int max_value = dp[target];return sum - max_value * 2;}
}

解題思路

這段代碼解決的是 "最后一塊石頭的重量 II" 問題，這是一個典型的動態規劃問題，本質上可以轉化為 0-1 背包問題。

算法思路解析：

1. 問題轉化：將石頭分成兩堆，使兩堆的重量盡可能接近總和的一半。這樣兩堆石頭碰撞后剩下的重量就是最小可能值。
2. 動態規劃思路：
   • 計算所有石頭的總重量 sum
   • 目標是找到總和不超過 sum/2 的最大子集和
   • 使用 0-1 背包的動態規劃方法求解這個最大子集和

代碼解釋：

• sum：計算所有石頭的總重量
• target：總重量的一半，作為背包的最大容量
• dp[j]：表示容量為 j 的背包能裝下的最大石頭重量
• 內層循環采用倒序遍歷j，是為了避免同一石頭被多次使用（0-1 背包特性）
• 最終結果sum - max_value * 2表示兩堆石頭碰撞后剩余的最小重量

LeetCode.494 目標和

題目鏈接?目標和

題解

class Solution {public int findTargetSumWays(int[] nums, int target) {int sum = 0;int len = nums.length;for(int i = 0;i<len;i++) sum += nums[i];if ((target + sum) % 2 == 1) return 0;if (Math.abs(target) > sum) return 0;int n = (sum + target) / 2;// 能湊成i容量的dp[i]種方法int[] dp = new int[n+1];dp[0] = 1;for(int i = 0;i<len;i++){for(int j = n;j>=nums[i];j--){dp[j] += dp[j - nums[i]];}} return dp[n];}
}

解題思路

這段代碼解決的是 "目標和" 問題，即通過給數組中的每個數字添加 "+" 或 "-"，使得它們的和等于目標值 target，計算有多少種不同的方法。

算法思路解析：

1. 問題轉化：假設數組中添加 "+" 的元素和為sumA，添加 "-" 的元素和為sumB，則有：

   • sumA - sumB = target
   • sumA + sumB = sum（數組總和）
     兩式相加可得?2*sumA = target + sum，即?sumA = (target + sum) / 2

2. 關鍵判斷：

   • 如果(target + sum)是奇數，無法整除，直接返回 0
   • 如果target的絕對值大于總和sum，也返回 0

3. 動態規劃思路：

   • 問題轉化為：從數組中選取若干元素，使其和等于sumA，計算有多少種選法
   • 這是一個典型的 "子集和計數" 問題，可用 0-1 背包的動態規劃方法解決

代碼解釋：

• sum：計算數組所有元素的總和
• n：即上述的sumA，表示需要湊出的目標和
• dp[i]：表示能湊成和為 i 的方法總數
• 初始化dp[0] = 1：表示湊成和為 0 的方法有 1 種（什么都不選）
• 內層循環倒序遍歷，避免同一元素被重復使用
• 最終結果dp[n]就是能湊成目標和的方法總數

LeetCode.474 一和零

題目鏈接?一和零

題解

class Solution {public int findMaxForm(String[] strs, int m, int n) {int[][][] dpArr = new int[strs.length][m + 1][n + 1];int zeroNum = 0;int oneNum = 0;for (char c : strs[0].toCharArray()) {if (c == '0') {zeroNum++;} else {oneNum++;}}for (int j = zeroNum; j <= m; j++) {for (int k = oneNum; k <= n; k++) {dpArr[0][j][k] = 1;}}for (int i = 1; i < strs.length; i++) {zeroNum = 0;oneNum = 0;for (char c : strs[i].toCharArray()) {if (c == '0') {zeroNum++;} else {oneNum++;}}for (int j = 0; j <= m; j++) {for (int k = 0; k <= n; k++) {if (j >= zeroNum && k >= oneNum) {dpArr[i][j][k] = Math.max(dpArr[i - 1][j][k], dpArr[i - 1][j - zeroNum][k - oneNum] + 1);} else {dpArr[i][j][k] = dpArr[i - 1][j][k];}}}}return dpArr[dpArr.length - 1][m][n];}
}

解題思路

這段代碼解決的是 "一和零" 問題，即在給定 0 和 1 的最大數量限制 (m 和 n) 的情況下，從字符串數組中選出最多數量的字符串，使這些字符串中包含的 0 總數不超過 m，1 總數不超過 n。

算法思路解析：

這是一個典型的二維 0-1 背包問題：

• 每個字符串可以看作一個物品
• 每個物品有兩個 "重量" 屬性：0 的數量和 1 的數量
• 背包的兩個容量限制分別是 m (0 的最大數量) 和 n (1 的最大數量)
• 目標是選擇最多數量的物品 (字符串) 而不超過背包容量

代碼解釋：

1. 三維 DP 數組定義：dpArr[i][j][k]表示在前 i 個字符串中，使用不超過 j 個 0 和 k 個 1 時能選取的最大字符串數量

2. 初始化處理：

   • 計算第一個字符串中 0 和 1 的數量
   • 對于能容納第一個字符串的所有 (j,k) 組合，初始化為 1 (表示選擇第一個字符串)

3. 狀態轉移：

   • 對每個字符串，先計算其包含的 0 和 1 的數量
   • 對每種可能的 0 和 1 的數量限制 (j,k)：
     • 如果當前字符串可以被容納 (j>= 0 的數量且 k >= 1 的數量)，則取 "不選當前字符串" 和 "選當前字符串" 兩種情況的最大值
     • 否則，只能繼承不選當前字符串的結果

4. 最終結果：dpArr[strs.length - 1][m][n]表示考慮所有字符串后，在 m 和 n 限制下能選取的最大字符串數量