动态规划 之 背包问题

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

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

• 通俗来说，可以这么理解，0-1背包问题，用于求解选择问题，结果存在一个target的限制
  • 传统的0-1背包问题，<=target下的最大价值数
  • 非连续子数列的=target的最长长度

• 两层循环，外层循环是我们的nums[i]，也就是可选的商品，内层循环是target也就是对于空间的遍历
  属于的是组合问题，要区别于排列问题，要是排列问题，外层循环是空间，内层循环是nums商品

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

• 0-1背包和完全背包的问题，总的来说递推公式十分相似，区别在于递推公式
  • 0-1背包问题是 $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][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的最大长度# 赋值为负无穷表示无法找到，不能全部都赋值为0dp = [[-inf]*(target+1) for _ in range(m+1)]# 分为选与不选的问题，dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i]] # 这个赋值很重要dp[0][0] = 0for 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 0m = s // 2n = len(nums)dp = [[0]*(m+1) for _ in range(n+1)]# 赋初值为1，不然后面算不了dp[0][0] = 1for 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] = 0for 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] = 1for 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是组合问题，当出现排序问题如何解决？参照下面的博客

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

多重背包

多重背包问题：在完全背包的基础上，限制每一个物品的数量，需要判断我们的空间j到底可以容纳下几个第i个物品，就有递推公式dp[i][j] = dp[i][j]+dp[i-1][j-z*marks]

2585.获得分数的方法数

2585.获得分数的方法数

思路分析：完全背包问题和0-1背包问题的结合，但是又有新的元素的出现，递推公式有所不同

• 0-1背包问题$dp[i][j]=dp[i-1][j]+dp[i-1][j-nums[i]]$
• 完全背包问题$dp[i][j]=dp[i-1][j]+dp[i][j-nums[i]]$
• 多重背包问题$dp[i][j]=dp[i][j]+dp[i-1][j-nums[i]\ast z]$
• 完全背包问题的累加的情况体现在dp[i][j-nums[i]],这个多重背包问题的累加体现在dp[i][j]

class Solution:def waysToReachTarget(self, target: int, types: List[List[int]]) -> int:# 完全背包问题，不过可以参照这个零钱兑换的思路去做，不过每次的时候要限制mod = 10**9 + 7n = len(types)dp = [[0]*(target+1) for _ in range(n+1)]dp[0][0] = 1# for i,c in enumerate(types):count,marks = c[0],c[1]for j in range(target+1):# 当不够的时候，那么就有 dp[i][j] = dp[i-1][j]dp[i+1][j] = dp[i][j]for z in range(1,count+1):if j >= z*marks:# 多重背包问题，dp[i][j] = dp[i][j] + dp[i-1][j-nums[i]*z]# 这个dp[i+1][j]最初始的值是外部的dp[i][j],我们得考虑选择z个的情况，每次都要加上之前的情况# 如果只是单纯的使用dp[i+1][j] = (dp[i][j] + dp[i][j - z * types[i][1]]) % mod# 那就是并没有正确累加先前的情况dp[i+1][j] = (dp[i+1][j] + dp[i][j - z * marks]) % modreturn dp[n][target]

分组背包

分组背包：就是有n组物品，每个物品的值都不一样，你可以选择一个物品

1155.掷骰子等于目标和的方法数

1155.掷骰子等于目标和的方法数

思路分析：

# 先放一个递归的方法
class Solution:def numRollsToTarget(self, n: int, k: int, target: int) -> int:mod = 10**9 + 7# 这个的意思是什么？一共有k种物体，k种物体加起来一共n个# 可以从递归入手，定义dfs(i,j)表示使用i个骰子，丢出j的点数# 当然，这个dfs(i,j) 可以由 dfs(i-1,j-1) + dfs(i-1,j-2)···+dfs(i-1,j-k)一起加起来# 递归返回的时候使用的是 i <=0 , j< i@cachedef dfs(i,j):# 得到结果，及时返回1if i == 0 and j == 0:return 1# i 不能<=0 ,同时要组合的结果j不能小于i,因为剩余i个骰子，最少也得是i(全部为1)if i <= 0 or j<i:return 0ans = 0# 枚举for z in range(1,k+1):ans += dfs(i-1,j-z)return ans % modreturn dfs(n,target) 

动态规划
灵神分析

class Solution:def numRollsToTarget(self, n: int, k: int, target: int) -> int:mod = 10**9 + 7           # 1:1 翻译为 动态规划,dp[i][j] 表示投掷出i个骰子，组合为点数j的方案数if not (n <= target <= n * k):return 0  # 无法组成 targetdp = [[0]*(target+1) for _ in range(n+1)]dp[0][0] = 1for i in range(n):# 遍历可以找得到的空间for j in range(target+1):for z in range(1,min(k+1,j+1)):dp[i+1][j] = (dp[i+1][j] + dp[i][j-z])%modreturn dp[n][-1]