動態規劃--背包問題匯總
- 2021 年 1 月 17 日
- 筆記
- Python, LeetCode請對我溫柔
刷LeetCode發現有幾題很像，參考laluladong的思想整理一下
- 474一和零
- 322零錢兌換 ( 待加入）
- 518 零錢兌換Ⅱ
- 416分割等和子集
- 1143最長公共子序列
解上面幾題的思路都很像，都是「背包問題」，無非就是所要求的目標不太相同。先大概看一下各個題目所求，詳細題目參見下文。
474、一和零：給你一個二進位字元串數組 strs 和兩個整數 m 和 n 。
請你找出並返回 strs 的最大子集的大小，該子集中 最多 有 m 個 0 和 n 個 1 。
518、零錢兌換Ⅱ ：給定不同面額的硬幣和一個總金額。寫出函數來計算可以湊成總金額的硬幣組合數。假設每一種面額的硬幣有無限個。
416、分割等和子集：給定一個只包含正整數的非空數組。是否可以將這個數組分割成兩個子集，使得兩個子集的元素和相等。轉化為：數組中是否有這樣的子集使得他們的和，恰好為數組中所有數字和的二分之一，即能否使一個背包容量為數字和/2的背包恰好裝滿。
1143、最長公共子序列：給定兩個字元串 text1 和 text2，返回這兩個字元串的最長公共子序列的長度。
圖解：
區別：
在背包能夠裝下當前的物品的情況下：
分割等和子集：
if (j < nums[i-1]): dp[i][j] = dp[i - 1][j] else: dp[i][j] = dp[i - 1][j] or dp[i - 1][j - nums[i-1]]#能裝下
一和零：
if j >= zeros and k >= ones : dp[i][j][k] = max( dp[i-1][j][k],dp[i - 1][j - zeros][k - ones] + 1)#能裝下 else: dp[i][j][k] = dp[i - 1][j][k]
零錢兌換Ⅱ
if(j<coins[i-1]): dp[i][j]=dp[i-1][j] else: dp[i][j]=dp[i-1][j]+dp[i][j-coins[i-1]]#能裝下
最長迴文子序列
if(bao[j-1]==things[i-1]): dp[i][j]=dp[i-1][j-1]+1#能裝 else: dp[i][j]=max(dp[i-1][j],dp[i][j-1])
可以看到一個小規律
在背包容量滿足當前這個物品的大小時，只有零錢兌換Ⅱ比較特殊，其他的三題都是在 i -1 的基礎上進行操作，即本物品之後一個，如果我要裝入背包，那麼我會在裝入之前的 i-1 個物品上進行+1或其他True False操作，而零錢兌換是在沒有本物品的基礎上+ dp[i][j-coins[i-1]] ，即加上用一張本面額，剩下的金額在包含本面額的面額種類數中的最大組合數，由於題目中已說明每種前有無數個，所以，就算用掉了本面額的錢數，在剩下的金額中還是可以使用本面額，所以是加 i 行，而不是加 i-1行，若每個面額的錢只有一張，那麼就是加 i -1行。
不滿足當前物品大小時，就比較類似了，都是繼承沒有該物品時的上一次的值，即 i -1 的值，
題目及程式碼詳情
1143最長公共子序列
給定兩個字元串 text1 和 text2，返回這兩個字元串的最長公共子序列的長度。
一個字元串的 子序列 是指這樣一個新的字元串：它是由原字元串在不改變字元的相對順序的情況下刪除某些字元（也可以不刪除任何字元）後組成的新字元串。
例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。兩個字元串的「公共子序列」是這兩個字元串所共同擁有的子序列。
若這兩個字元串沒有公共子序列，則返回 0。
例：
輸入：text1 = "abcde", text2 = "ace"
輸出：3
解釋：最長公共子序列是 "ace"，它的長度為 3。
來源：力扣（LeetCode）
鏈接：//leetcode-cn.com/problems/longest-common-subsequence
class Solution(object): def longestCommonSubsequence(self, text1, text2): if not text2 or not text1: return 0 bao=text1 things=text2 if len(text1)<len(text2): bao= text2 things=text1 dp= [[0 for _ in range(len(bao)+1)]for _ in range(len(things)+1)] for i in range(1,1+len(things)): for j in range(1,1+len(bao)): if(bao[j-1]==things[i-1]): dp[i][j]=dp[i-1][j-1]+1 else: dp[i][j]=max(dp[i-1][j],dp[i][j-1]) return dp[-1][-1]
分割等和子集
給定一個只包含正整數的非空數組。是否可以將這個數組分割成兩個子集，使得兩個子集的元素和相等。
注意:
每個數組中的元素不會超過 100
數組的大小不會超過 200
例：
輸入: [1, 5, 11, 5]
輸出: true
解釋: 數組可以分割成 [1, 5, 5] 和 [11].
來源：力扣（LeetCode）
鏈接：//leetcode-cn.com/problems/partition-equal-subset-sum
class Solution(object): def canPartition(self, nums): n = sum(nums) if (n % 2 != 0): return False else: n /= 2 dp = [[False for i in range(n + 1)] for j in range(len(nums)+1)] for t in range(len(nums)): dp[t][0] = True for i in range(1,len(nums)+1): for j in range(1, n + 1): if (j - nums[i-1] < 0): dp[i][j] = dp[i - 1][j] else: dp[i][j] = dp[i - 1][j] or dp[i - 1][j - nums[i-1]] return dp[-1][-1]
一和零
給你一個二進位字元串數組 strs 和兩個整數 m 和 n 。
請你找出並返回 strs 的最大子集的大小，該子集中 最多 有 m 個 0 和 n 個 1 。
如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。
例：
輸入：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 。
來源：力扣（LeetCode）
鏈接：//leetcode-cn.com/problems/ones-and-zeroes
class Solution(object): def findMaxForm(self, strs, m, n): dp = [[[0] * (n + 1) for _ in range(m + 1)] for _ in range(len(strs) + 1)] for i in range(1, len(strs) + 1): ones = strs[i - 1].count("1") zeros = strs[i - 1].count("0") for j in range(m + 1): for k in range(n + 1): if j >= zeros and k >= ones : dp[i][j][k] = max( dp[i-1][j][k],dp[i - 1][j - zeros][k - ones] + 1) else: dp[i][j][k] = dp[i - 1][j][k] return dp[-1][-1][-1]
零錢兌換Ⅱ
給定不同面額的硬幣和一個總金額。寫出函數來計算可以湊成總金額的硬幣組合數。假設每一種面額的硬幣有無限個。
例：
輸入: amount = 5, coins = [1, 2, 5]
輸出: 4
解釋: 有四種方式可以湊成總金額:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
來源：力扣（LeetCode）
鏈接：//leetcode-cn.com/problems/coin-change-2
python程式碼
class Solution(object): def change(self, m, coins): dp = [[0 for _ in range(m + 1)] for _ in range(len(coins) + 1)] for i in range(len(coins) + 1): dp[i][0] = 1 for i in range(1, len(coins) + 1): for j in range(1, m + 1): if(j<coins[i-1]): dp[i][j]=dp[i-1][j] else: dp[i][j]=dp[i-1][j]+dp[i][j-coins[i-1]] return dp[-1][-1]
