背包問(wèn)題是動(dòng)態(tài)規(guī)劃一個(gè)很重要的一類(lèi)題目，主要分為0-1背包問(wèn)題以及完全背包問(wèn)題

基礎(chǔ)的知識(shí)請(qǐng)看另一個(gè)博客
動(dòng)態(tài)規(guī)劃之背包問(wèn)題

• 通俗來(lái)說(shuō)，可以這么理解，0-1背包問(wèn)題，用于求解選擇問(wèn)題，結(jié)果存在一個(gè)target的限制
  • 傳統(tǒng)的0-1背包問(wèn)題，<=target下的最大價(jià)值數(shù)
  • 非連續(xù)子數(shù)列的=target的最長(zhǎng)長(zhǎng)度

• 兩層循環(huán)，外層循環(huán)是我們的nums[i]，也就是可選的商品，內(nèi)層循環(huán)是target也就是對(duì)于空間的遍歷
  屬于的是組合問(wèn)題，要區(qū)別于排列問(wèn)題，要是排列問(wèn)題，外層循環(huán)是空間，內(nèi)層循環(huán)是nums商品

對(duì)于這個(gè)排列還是組合的問(wèn)題，請(qǐng)看我的另一博客
動(dòng)態(tài)規(guī)劃 之 排列與組合問(wèn)題

• 0-1背包和完全背包的問(wèn)題，總的來(lái)說(shuō)遞推公式十分相似，區(qū)別在于遞推公式
  • 0-1背包問(wèn)題是 $dp[i][j]=max(dp[i?1][j],dp[i?1][j?w[i]]+v[i])$
  • 完全背包問(wèn)題是 $dp[i][j]=max(dp[i?1][j],dp[i][j?w[i]]+v[i])$
• 如何理解？
• 答：在0-1背包問(wèn)題中，對(duì)于選與不選當(dāng)前的元素nums[i],我們都只需考慮前i-1個(gè)物品的情況，所以是max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]);但是對(duì)于完全背包問(wèn)題的時(shí)候，不選當(dāng)前的nums[i],我們就是只需考慮前i-1個(gè)物品，否則就是得考慮前i個(gè)物品的情況，所以是max(dp[i-1][j], dp[i][j-w[i]] + v[i])

0-1背包問(wèn)題

2915.和為目標(biāo)值的最長(zhǎng)子序列的長(zhǎng)度

2915.和為目標(biāo)值的最長(zhǎng)子序列的長(zhǎng)度

思路分析：由于子序列是運(yùn)行非連續(xù)的，并且又是求解的是值為target的最長(zhǎng)長(zhǎng)度，我們就可以思考，如何縮小化我們的問(wèn)題？定義dp[i][j]表示前i種商品中，值為j的最長(zhǎng)的長(zhǎng)度，那么一個(gè)dp[i][j]就可以由前面的dp[i-1][j]和dp[i-1][j-nums[i]]+1的較大值轉(zhuǎn)移而來(lái)

class Solution:def lengthOfLongestSubsequence(self, nums: List[int], target: int) -> int:# dp[i][j] 定義為 前i種物品中，價(jià)值為j的方案數(shù)# 0-1 背包問(wèn)題 的遞推公式 當(dāng) j >= nums[i] 的時(shí)候， m = len(nums)# 典型的一個(gè)0-1背包問(wèn)題# 定義dp[i][j] 表示前i個(gè)物品中，和為j的最大長(zhǎng)度# 賦值為負(fù)無(wú)窮表示無(wú)法找到，不能全部都賦值為0dp = [[-inf]*(target+1) for _ in range(m+1)]# 分為選與不選的問(wèn)題，dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i]] # 這個(gè)賦值很重要dp[0][0] = 0for i in range(m):for j in range(target+1):# 當(dāng)無(wú)法更新的時(shí)候，dp的值就是前i-1的時(shí)候相同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.目標(biāo)和

494.目標(biāo)和

思路分析：這題明面上，要你選擇要加的數(shù)和減去的數(shù)字，實(shí)際上你可以通過(guò)轉(zhuǎn)化，為只用求解要加上的數(shù)字或者要減去的數(shù)字為對(duì)應(yīng)轉(zhuǎn)化之后的一個(gè)newtarget，然后照著2915.和為目標(biāo)值的最長(zhǎng)子序列的長(zhǎng)度一樣的思路去做，不過(guò)由于這題求解的是方案數(shù)，所以對(duì)應(yīng)的遞推公式以及初始值不一樣

詳細(xì)的分析參考靈神的分析

class Solution:def findTargetSumWays(self, nums: List[int], target: int) -> int:# 類(lèi)似于0-1背包問(wèn)題，求解的是運(yùn)算結(jié)果等于target的表達(dá)式的數(shù)目# 我們可以照常選擇正數(shù)zheng，那么對(duì)應(yīng)的負(fù)數(shù)就是sum(nums) - zheng# dp[i][j] 定義為前i個(gè)數(shù)字中，值為j的數(shù)目# dp[i][j] = dp[i-1][j-nums[i]] + dp[i-1][j+nums[i]] ,計(jì)算nums[i]=0也沒(méi)關(guān)系，+，-0算兩個(gè)表達(dá)式# 那么dp數(shù)組怎么開(kāi)這個(gè)target,原本的困惑，就是選了正數(shù)還要管這個(gè)target的范圍# 由式子，選取正數(shù)的和為p,要減去的數(shù)字和為q,有p+q=s,p-q = target，就可以求解出p與q的值即可# 我們只要開(kāi)的空間等于其中一個(gè)即可,也可以去一個(gè)絕對(duì)值都算上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]

完全背包問(wèn)題

322.零錢(qián)兌換

322.零錢(qián)兌換

思路分析：這是一個(gè)完全背包問(wèn)題，老樣子，由于求解的是最小數(shù)目，所以初始值我們?cè)O(shè)置為float('inf'),然后再初始化dp[0][0]=1

class Solution:def coinChange(self, coins: List[int], amount: int) -> int:# 最少的硬幣數(shù)目，硬幣可以重復(fù)選，所以是完全背包問(wèn)題n = len(coins)dp = [[float('inf')]*(amount+1) for _ in range(n+1)]# 定義遞推公式，dp[i][j]表示前i種硬幣，組成面值為j的最少硬幣數(shù)目# 當(dāng)j>= nums[i] 的時(shí)候，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.零錢(qián)兌換II

518.零錢(qián)兌換II

思路分析：完全背包問(wèn)題，與322.零錢(qián)兌換的區(qū)別是，后者求解是最少的硬幣數(shù)，而本題求解的是 達(dá)到amount的方案數(shù)，兩種問(wèn)題帶來(lái)的dp數(shù)組的初始值和dp[0][0]的值不一樣

• 當(dāng)求解的是類(lèi)似于322.零錢(qián)兌換的達(dá)到amount的最少硬幣數(shù)，初始值為float('inf'),dp[0][0]=0
• 當(dāng)求解的是類(lèi)似于518.零錢(qián)兌換II的達(dá)到amount的方案數(shù),初始值為0,dp[0][0]=1

class Solution:def change(self, amount: int, coins: List[int]) -> int:# 區(qū)別與零錢(qián)兌換I，這個(gè)求解的是組合數(shù)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]

• 這個(gè)零錢(qián)兌換II是組合問(wèn)題，當(dāng)出現(xiàn)排序問(wèn)題如何解決？參照下面的博客

動(dòng)態(tài)規(guī)劃 之 排列與組合問(wèn)題

多重背包

多重背包問(wèn)題：在完全背包的基礎(chǔ)上，限制每一個(gè)物品的數(shù)量，需要判斷我們的空間j到底可以容納下幾個(gè)第i個(gè)物品，就有遞推公式dp[i][j] = dp[i][j]+dp[i-1][j-z*marks]

2585.獲得分?jǐn)?shù)的方法數(shù)

2585.獲得分?jǐn)?shù)的方法數(shù)

思路分析：完全背包問(wèn)題和0-1背包問(wèn)題的結(jié)合，但是又有新的元素的出現(xiàn)，遞推公式有所不同

• 0-1背包問(wèn)題$dp[i][j]=dp[i?1][j]+dp[i?1][j?nums[i]]$
• 完全背包問(wèn)題$dp[i][j]=dp[i?1][j]+dp[i][j?nums[i]]$
• 多重背包問(wèn)題$dp[i][j]=dp[i][j]+dp[i?1][j?nums[i]?z]$
• 完全背包問(wèn)題的累加的情況體現(xiàn)在dp[i][j-nums[i]],這個(gè)多重背包問(wèn)題的累加體現(xiàn)在dp[i][j]

class Solution:def waysToReachTarget(self, target: int, types: List[List[int]]) -> int:# 完全背包問(wèn)題，不過(guò)可以參照這個(gè)零錢(qián)兌換的思路去做，不過(guò)每次的時(shí)候要限制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):# 當(dāng)不夠的時(shí)候，那么就有 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:# 多重背包問(wèn)題，dp[i][j] = dp[i][j] + dp[i-1][j-nums[i]*z]# 這個(gè)dp[i+1][j]最初始的值是外部的dp[i][j],我們得考慮選擇z個(gè)的情況，每次都要加上之前的情況# 如果只是單純的使用dp[i+1][j] = (dp[i][j] + dp[i][j - z * types[i][1]]) % mod# 那就是并沒(méi)有正確累加先前的情況dp[i+1][j] = (dp[i+1][j] + dp[i][j - z * marks]) % modreturn dp[n][target]

分組背包

分組背包：就是有n組物品，每個(gè)物品的值都不一樣，你可以選擇一個(gè)物品

1155.擲骰子等于目標(biāo)和的方法數(shù)

1155.擲骰子等于目標(biāo)和的方法數(shù)

思路分析：

# 先放一個(gè)遞歸的方法
class Solution:def numRollsToTarget(self, n: int, k: int, target: int) -> int:mod = 10**9 + 7# 這個(gè)的意思是什么？一共有k種物體，k種物體加起來(lái)一共n個(gè)# 可以從遞歸入手，定義dfs(i,j)表示使用i個(gè)骰子，丟出j的點(diǎn)數(shù)# 當(dāng)然，這個(gè)dfs(i,j) 可以由 dfs(i-1,j-1) + dfs(i-1,j-2)···+dfs(i-1,j-k)一起加起來(lái)# 遞歸返回的時(shí)候使用的是 i <=0 , j< i@cachedef dfs(i,j):# 得到結(jié)果，及時(shí)返回1if i == 0 and j == 0:return 1# i 不能<=0 ,同時(shí)要組合的結(jié)果j不能小于i,因?yàn)槭Ｓ鄆個(gè)骰子，最少也得是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) 

動(dòng)態(tài)規(guī)劃
靈神分析

class Solution:def numRollsToTarget(self, n: int, k: int, target: int) -> int:mod = 10**9 + 7           # 1:1 翻譯為 動(dòng)態(tài)規(guī)劃,dp[i][j] 表示投擲出i個(gè)骰子，組合為點(diǎn)數(shù)j的方案數(shù)if not (n <= target <= n * k):return 0  # 無(wú)法組成 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]