动态规划–背包问题汇总
- 2021 年 1 月 17 日
- 筆記
- LeetCode请对我温柔, Python
刷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]
