动态规划之背包问题

文章目录 0-1背包问题2915.和为目标值的最长子序列的长度494.目标和 完全背包问题322.零钱兑换518.零钱兑换II 多重背包分组背包

背包问题是动态规划一个很重要的一类题目，主要分为0-1背包问题以及完全背包问题

基础的知识请看另一个博客 动态规划之背包问题

通俗来说，可以这么理解，0-1背包问题，用于求解选择问题，结果存在一个target的限制 传统的0-1背包问题，<=target下的最大价值数非连续子数列的=target的最长长度 两层循环，外层循环是我们的nums[i]，也就是可选的商品，内层循环是target也就是对于空间的遍历 属于的是组合问题，要区别于排列问题，要是排列问题，外层循环是空间，内层循环是nums商品

对于这个排列还是组合的问题，请看我的另一博客 动态规划 之 排列与组合问题

0-1背包和完全背包的问题，总的来说递推公式十分相似，区别在于递推公式 0-1背包问题是 d p [ i ] [ j ] = m a x ( d p [ i − 1 ] [ j ] , d p [ i − 1 ] [ j − w [ i ] ] + v [ i ] ) dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]) dp[i][j]=max(dp[i−1][j],dp[i−1][j−w[i]]+v[i])完全背包问题是 d p [ i ] [ j ] = m a x ( d p [ i − 1 ] [ j ] , d p [ i ] [ j − w [ i ] ] + v [ i ] ) dp[i][j] = max(dp[i-1][j], dp[i][j-w[i]] + v[i]) dp[i][j]=max(dp[i−1][j],dp[i][j−w[i]]+v[i]) 如何理解？答：在0-1背包问题中，对于选与不选当前的元素nums[i],我们都只需考虑前i-1个物品的情况，所以是max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]);但是对于完全背包问题的时候，不选当前的nums[i],我们就是只需考虑前i-1个物品，否则就是得考虑前i个物品的情况，所以是max(dp[i-1][j], dp[i][j-w[i]] + v[i]) 0-1背包问题 2915.和为目标值的最长子序列的长度

2915.和为目标值的最长子序列的长度

思路分析：由于子序列是运行非连续的，并且又是求解的是值为target的最长长度，我们就可以思考，如何缩小化我们的问题？定义dp[i][j]表示前i种商品中，值为j的最长的长度，那么一个dp[i][j]就可以由前面的dp[i-1][j]和dp[i-1][j-nums[i]]+1的较大值转移而来

class Solution: def lengthOfLongestSubsequence(self, nums: List[int], target: int) -> int: # dp[i][j] 定义为 前i种物品中，价值为j的方案数 # 0-1 背包问题 的递推公式 当 j >= nums[i] 的时候， m = len(nums) # 典型的一个0-1背包问题 # 定义dp[i][j] 表示前i个物品中，和为j的最大长度 # 赋值为负无穷表示无法找到，不能全部都赋值为0 dp = [[-inf]*(target+1) for _ in range(m+1)] # 分为选与不选的问题，dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i]] # 这个赋值很重要 dp[0][0] = 0 for i in range(m): for j in range(target+1): # 当无法更新的时候，dp的值就是前i-1的时候相同 if j < nums[i]: dp[i+1][j] = dp[i][j] else: # 原本的递推公式 dp[i][j] = max(dp[i-1][j],dp[i-1][j-nums[i]]+1) dp[i+1][j] = max(dp[i][j], dp[i][j-nums[i]]+1) return dp[m][target] if dp[m][target] > 0 else -1 494.目标和

494.目标和

思路分析：这题明面上，要你选择要加的数和减去的数字，实际上你可以通过转化，为只用求解要加上的数字或者要减去的数字为对应转化之后的一个newtarget，然后照着2915.和为目标值的最长子序列的长度一样的思路去做，不过由于这题求解的是方案数，所以对应的递推公式以及初始值不一样

详细的分析参考灵神的分析

class Solution: def findTargetSumWays(self, nums: List[int], target: int) -> int: # 类似于0-1背包问题，求解的是运算结果等于target的表达式的数目 # 我们可以照常选择正数zheng，那么对应的负数就是sum(nums) - zheng # dp[i][j] 定义为前i个数字中，值为j的数目 # dp[i][j] = dp[i-1][j-nums[i]] + dp[i-1][j+nums[i]] ,计算nums[i]=0也没关系，+，-0算两个表达式 # 那么dp数组怎么开这个target,原本的困惑，就是选了正数还要管这个target的范围 # 由式子，选取正数的和为p,要减去的数字和为q,有p+q=s,p-q = target，就可以求解出p与q的值即可 # 我们只要开的空间等于其中一个即可,也可以去一个绝对值都算上 s = sum(nums) - abs(target) if s<0 or s%2 == 1: return 0 m = s // 2 n = len(nums) dp = [[0]*(m+1) for _ in range(n+1)] # 赋初值为1，不然后面算不了 dp[0][0] = 1 for i in range(n): for j in range(m+1): if j < nums[i]: dp[i+1][j] = dp[i][j] else: # dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i]] dp[i+1][j] = dp[i][j] + dp[i][j-nums[i]] return dp[n][m] 完全背包问题 322.零钱兑换

322.零钱兑换

思路分析：这是一个完全背包问题，老样子，由于求解的是最小数目，所以初始值我们设置为float('inf'),然后再初始化dp[0][0]=1

class Solution: def coinChange(self, coins: List[int], amount: int) -> int: # 最少的硬币数目，硬币可以重复选，所以是完全背包问题 n = len(coins) dp = [[float('inf')]*(amount+1) for _ in range(n+1)] # 定义递推公式，dp[i][j]表示前i种硬币，组成面值为j的最少硬币数目 # 当j>= nums[i] 的时候，dp[i][j] = min(dp[i-1][j],dp[i][j-nums[i]]) dp[0][0] = 0 for i in range(n): for j in range(amount+1): if j < coins[i]: # 原本dp[i][j] = dp[i-1][j] dp[i+1][j] = dp[i][j] else: # 原本dp[i][j] = min(dp[i-1][j],dp[i][j-nums[i]]+1) dp[i+1][j] = min(dp[i][j],dp[i+1][j-coins[i]]+1) return dp[n][amount] if dp[n][amount] != float('inf') else -1 518.零钱兑换II

518.零钱兑换II

思路分析：完全背包问题，与322.零钱兑换的区别是，后者求解是最少的硬币数，而本题求解的是 达到amount的方案数，两种问题带来的dp数组的初始值和dp[0][0]的值不一样

当求解的是类似于322.零钱兑换的达到amount的最少硬币数，初始值为float('inf'),dp[0][0]=0当求解的是类似于518.零钱兑换II的达到amount的方案数,初始值为0,dp[0][0]=1 class Solution: def change(self, amount: int, coins: List[int]) -> int: # 区别与零钱兑换I，这个求解的是组合数 n = len(coins) dp = [[0]*(amount+1) for _ in range(n+1)] dp[0][0] = 1 for i in range(n): for j in range(amount+1): if j < coins[i]: # dp[i][j] = dp[i-1][j] dp[i+1][j] = dp[i][j] else: # dp[i][j] = dp[i-1][j] + dp[i][j-coins[i]] dp[i+1][j] = dp[i][j] + dp[i+1][j-coins[i]] return dp[n][amount] 这个零钱兑换II是组合问题，当出现排序问题如何解决？参照下面的博客

动态规划 之 排列与组合问题

多重背包 分组背包