代碼隨想錄算法訓(xùn)練營第四十二天 | LeetCode 1049. 最后一塊石頭的重量 II、494. 目標(biāo)和、474. 一和零

文章鏈接：最后一塊石頭的重量 II 目標(biāo)和 一和零
視頻鏈接：最后一塊石頭的重量 II 目標(biāo)和 一和零

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

1.1 思路

1. 這題不要被題目的示例給帶偏，其實(shí)就是看看我們能不能把石頭盡量分成兩堆，比如示例的總和為 23，看看能不能分成一半就是 11，另一半就是 12 了，一相撞就是剩下 1 了。即盡量分成重量總和近似相等的兩堆，就是想到本題的關(guān)鍵了，這么看和416. 分割等和子集還是很像的，區(qū)別就是那題是能分成子集相等的就是 true 反之 false，本題是盡量湊，湊不成就相撞所剩下的重量也是最小的。
2. dp 數(shù)組的下標(biāo)及其含義：在 01 背包中，背包容量為 j 所能帶的最大價值為 dp[j]。但本題的重量/容量也是它的價值，所以這里的最大價值也是它的最大重量，背包容量為 j 所能帶的最大重量為 dp[j]
3. 遞推公式：在 01 背包中，dp[j]=Math.max（dp[j]，dp[j-weight[i]]+value[i]），前者是不放物品 i，后者是放物品 i。在本題中 dp[j]=Math.max（dp[j]，dp[j-stones[i]]+stones[i]），前者是不放石頭 i，后者是放石頭 i
4. dp 數(shù)組的初始化：dp[0]=0，容量 0 的背包能放的重量也是 0。其他下標(biāo)初始化為 0，因?yàn)槲覀兊倪f推公式是通過別的值覆蓋 dp[j] 的，因此不能初始化太大，為 0 最正確。我們這里定義 dp 數(shù)組的大小就是，先求 sum，target=sum/2，dp 數(shù)組的大小就是 target+1，因?yàn)槲覀円獪惾萘康囊话?/li>
5. 遍歷順序：兩層 for循環(huán)，for（int i=0；i<stones.length；i++）for（int j=target；j>=stones[i]；j–）先物品后背包，然后背包這一層從后往前遍歷，這里為什么j>=stones[i] 是因?yàn)槿绻嘲萘勘仁^重量還小再遍歷就沒有意義了
6. 打印 dp 數(shù)組：用于 debug
7. 最后 return sum-2*dp[target]

1.2 代碼

class Solution {public int lastStoneWeightII(int[] stones) {int sum = 0;for (int i : stones) {sum += i;}int target = sum >> 1;//初始化dp數(shù)組int[] dp = new int[target + 1];for (int i = 0; i < stones.length; i++) {//采用倒序for (int j = target; j >= stones[i]; j--) {//兩種情況，要么放，要么不放dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);}}return sum - 2 * dp[target];}
}

2. LeetCode 494. 目標(biāo)和

2.1 思路

1. 我們可以在集合中加入“+”“-”變?yōu)橐粋€表達(dá)式，使其等于我們的 target。關(guān)于放“+”還是“-”就是把這個集合分成了兩個集合，放加法的是一個集合，放減法的是一個集合。本題和416. 分割等和子集也是一個集合里分兩個子集還有1049. 最后一塊石頭的重量 II也是一個集合里分出兩個子集。本題中我們加法用 left，減法用 right，加法和減法的集合就是原集合的總和 sum，要求加法集合 left-減法集合 right=target，一相加就是 2left=sum+target => 即 left=（sum+target）/2。舉例 [1,1,1,1,1] 即 sum=5，題目的 target=3，因此 left=（5+3）/2，就是 4 個用加法，1 個用減法，我們求出 left 集合剩下的就是 right 集合了。當(dāng)然也是有用例是求不出 left 集合的，比如如果上面的是 target=2，那我們的 left 和 right 都找不到一種匹配的集合等于 target，因此如果判斷出 （target+sum）%2！=0 就最終輸出 0。此時問題轉(zhuǎn)化為，求出 left 集合，原集合里所有元素裝滿這個 left 集合有多少種方法，就能找到符合題目條件的多少種組合，這就是背包問題了，left 就是背包容量，原集合就是我們的物品
2. 純 01 背包就是問裝滿這個背包的最大價值，416. 分割等和子集就是能不能裝滿這個背包，滿了就 true 否則就 false，1049. 最后一塊石頭的重量 II結(jié)束盡量去裝，能裝多少裝多少，本題就是給我們一個容量，問有多少種方式能把背包裝滿
3. dp 數(shù)組及其下標(biāo)的含義：dp[j] 裝滿背包容量為 j 有 dp[j] 種方法。bagSize=（target+sum）/2
4. 遞推公式：dp[j]+=dp[j-nums[i]]

5. dp 數(shù)組的初始化：在 01 背包中 dp[0] 初始化為 0，即背包容量為 0 的背包最大價值是 0，但是本題，dp[0] 應(yīng)該初始化為 1，因?yàn)槲覀兊?dp[j] 是通過前面累加的，如果初始化為 0，后面就一直是 0 了
6. 遍歷順序：01 背包中先物品再背包，因此 for（int i=0；i<nums.length；i++）for（int j=bagSize；j>=nums[i]；j–）第二層倒序遍歷，然后 dp[j]+=dp[j-nums[i]]
7. 打印 dp 數(shù)組：用于 debug

2.2 代碼

class Solution {public int findTargetSumWays(int[] nums, int target) {int sum = 0;for (int i = 0; i < nums.length; i++) sum += nums[i];//如果target過大 sum將無法滿足if ( target < 0 && sum < -target) return 0;if ((target + sum) % 2 != 0) return 0;int size = (target + sum) / 2;if(size < 0) size = -size;int[] dp = new int[size + 1];dp[0] = 1;for (int i = 0; i < nums.length; i++) {for (int j = size; j >= nums[i]; j--) {dp[j] += dp[j - nums[i]];}}return dp[size];}
}

3. LeetCode 474. 一和零

3.1 思路

1. 本題讓我們從題目的集合中找出一個最多元素的子集，滿足有 m 個 0，n 個 1?？梢园?m 個 0 和 n 個 1 理解為一個背包，有兩個維度，最多有 m 個 0 和 n 個 1，而集合里的元素就是物品。但這題不是多重背包，還是 01 背包，每個物品只能是使用 1 次，只是有兩個維度。而多重背包是會限制物品的個數(shù)。
2. 純 01 背包就是問裝滿這個背包的最大價值，416. 分割等和子集就是能不能裝滿這個背包，滿了就 true 否則就 false，1049. 最后一塊石頭的重量 II結(jié)束盡量去裝，能裝多少裝多少，494. 目標(biāo)和就是給我們一個容量，問有多少種方式能把背包裝滿，本題是求裝滿這個背包最多有多少個物品
3. dp 數(shù)組及其下標(biāo)的含義：我們是要裝滿一個 m 個 0、n 個 1 這么大容器的背包，這個背包里最多有多少個物品，一共 3 個變量，m、n、多少個物品。兩個維度 m 個 0、n 個 1，因此定義個二維 dp 數(shù)組，含義是最多有 i 個 0 j 個 1 的 strs 的最多有 dp[i][j] 個物品，最終 dp[m][n] 就是我們的結(jié)果
4. 遞推公式：純 01 背包的公式是 dp[j]=Math.max（dp[j]，dp[j-weight[i]]+value[i]），本題中我們物品的重量就是 x 個 0 y 個 1，整個背包最大重量是 m 個 0 n 個 1。因此 dp[i-x][j-y]+1，這里減去的 x 和 y 就是物品的重量，+1 就是物品的價值，價值就是個數(shù)，我們求的就是最多個數(shù)?？梢赃@么理解：放了物品 i，還剩下 j - weight[i] 的容量可以放其他物品，剩下空間能得到的最大價值是 dp[i-1][j-weight[i]] 這句話是引用 01 背包理論基礎(chǔ)的，理解一下。因此 dp[i][j]=Math.max（dp[i][j]， dp[i-x][j-y]+1）
5. dp 數(shù)組的初始化：dp[0][0]=0，背包容量為 0 了，最大的物品個數(shù)自然也是 0。非 0 下標(biāo) dp[i][j] 物品個數(shù)不會是負(fù)數(shù)，因此初始化為 0，就不會在遞推時 dp[i][j] 被初始化值覆蓋掉
6. 遍歷順序：也是"兩層"for循環(huán)，先物品再背包。先通過增強(qiáng) for循環(huán)遍歷 str，每遍歷到一個物品就要用 x 和 y 記錄有幾個 0 和 1。然后就是遍歷背包，這里是要遍歷 0 和 1，我們是先 0 再 1，不過可以顛倒，但是要倒序遍歷， for（int i=m；i>=x；i–）for（int j=n；j>=y；j–）
7. 打印 dp 數(shù)組：用于 debug

3.2 代碼

class Solution {public int findMaxForm(String[] strs, int m, int n) {//dp[i][j]表示i個0和j個1時的最大子集int[][] dp = new int[m + 1][n + 1];int oneNum, zeroNum;for (String str : strs) {oneNum = 0;zeroNum = 0;for (char ch : str.toCharArray()) {if (ch == '0') {zeroNum++;} else {oneNum++;}}//倒序遍歷for (int i = m; i >= zeroNum; i--) {for (int j = n; j >= oneNum; j--) {dp[i][j] = Math.max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);}}}return dp[m][n];}
}