當(dāng)然拿到問(wèn)題后，需要做到以下幾個(gè)步驟：
1.分析是否為背包問(wèn)題玛迄。
2.是三種背包問(wèn)題中的哪一種卵沉。
3.是0-1背包問(wèn)題還是完全背包問(wèn)題。也就是題目給的nums數(shù)組中的元素是否可以重復(fù)使用乒疏。
4.如果是組合問(wèn)題额衙，是否需要考慮元素之間的順序。需要考慮順序有順序的解法怕吴，不需要考慮順序又有對(duì)應(yīng)的解法窍侧。
三種背包問(wèn)題
組合問(wèn)題公式
dp[i] += dp[i-num]
True、False問(wèn)題公式
dp[i] = dp[i] or dp[i-num]
最大最小問(wèn)題公式
dp[i] = min(dp[i], dp[i-num]+1)或者dp[i] = max(dp[i], dp[i-num]+1)
以上三組公式是解決對(duì)應(yīng)問(wèn)題的核心公式转绷。
背包問(wèn)題的判定
背包問(wèn)題具備的特征：給定一個(gè)target伟件，target可以是數(shù)字也可以是字符串，再給定一個(gè)數(shù)組nums议经，nums中裝的可能是數(shù)字斧账，也可能是字符串，問(wèn)：能否使用nums中的元素做各種排列組合得到target煞肾。
背包問(wèn)題技巧：
1.如果是0-1背包咧织，即數(shù)組中的元素不可重復(fù)使用，nums放在外循環(huán)籍救，target在內(nèi)循環(huán)习绢，且內(nèi)循環(huán)倒序；
for num in nums:
for i in range(target, nums-1, -1):
2.如果是完全背包蝙昙，即數(shù)組中的元素可重復(fù)使用闪萄，nums放在外循環(huán)，target在內(nèi)循環(huán)耸黑。且內(nèi)循環(huán)正序桃煎。
for num in nums:
for i in range(nums, target+1):
3.如果組合問(wèn)題需考慮元素之間的順序，需將target放在外循環(huán)大刊，將nums放在內(nèi)循環(huán)为迈。
for i in range(1, target+1):
for num in nums:
以上內(nèi)容來(lái)自希望用一種規(guī)律搞定背包問(wèn)題---Jackie1995三椿，下面介紹一些例題。
0-1背包問(wèn)題
給定種物品和一個(gè)背包葫辐，物品
的重量是
,其價(jià)值為
,背包的容量為
搜锰。問(wèn)應(yīng)該如何選擇裝入背包的物品使得裝入背包中的物品總價(jià)值最大？
在選擇裝入背包的物品時(shí)耿战，對(duì)每種物品只有兩種選擇蛋叼，即裝入背包或者不裝入背包。不能將物品
裝入背包多次剂陡，也不能只裝入部分的物品i狈涮。
[分析]表示前
件物品恰放入一個(gè)容量為
的背包可以獲得
的最大價(jià)值。
（1）當(dāng)時(shí)鸭栖，
（2）當(dāng)時(shí)歌馍，每個(gè)物品都有0-1兩種狀態(tài)，則其狀態(tài)轉(zhuǎn)移方程便是:
[湊硬幣問(wèn)題]
有1元晕鹊，2元松却，5元硬幣若干，湊到20元最少需要多少枚硬幣溅话。
(1)時(shí)晓锻，需要0個(gè)硬幣，
(2)時(shí)飞几，考慮最后一次硬幣硬幣情況砚哆，向前分析，即可得狀態(tài)轉(zhuǎn)移方程:
def detectMinCoins(M,coins):
dp = [0]*(M+1)
for N in range(1,M+1):
l = []
for i in coins:
if N>=i:
l.append(dp[N-i]+1)
dp[N] = min(l)
return dp[M]
硬幣問(wèn)題
給定數(shù)量不限的硬幣循狰，幣值為25分窟社、10分、5分和1分绪钥，編寫(xiě)代碼計(jì)算n分有幾種表示法。(結(jié)果可能會(huì)很大关炼，你需要將結(jié)果模上1000000007)
[分析]
dp[i][j] 使用前i種硬幣計(jì)算j分的表示法種數(shù) 令coins=[25, 10, 5, 1]
dp[i][j] = dp[i-1][j] + dp[i-1][j-coins[i]] + dp[i-1][j-2*coins[i]] + ... dp[i-1][j-k*coins[i]]
j >= k*coins[i]
dp[i][j-coins[i]] = dp[i-1][j-coins[i]] + dp[i-1][j-2*coins[i]] + ... dp[i-1][j-k*coins[i]]
dp[i][j] - dp[i][j-coins[i]] = dp[i-1][j]
dp[i][j] = dp[i][j-coins[i]] + dp[i-1][j]
舉個(gè)例子程腹，當(dāng)n=10時(shí)
| coin\n | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 5 | 1 | 1 | 1 | 1 | 1 | 2 | 2 | 2 | 2 | 2 | 3 |
| 10 | 1 | 1 | 1 | 1 | 1 | 2 | 2 | 2 | 2 | 2 | 4 |
| 25 | 1 | 1 | 1 | 1 | 1 | 2 | 2 | 2 | 2 | 2 | 4 |
簡(jiǎn)化問(wèn)題，只需要得出最后一行即可儒拂。
def detectMinCoins(M,coins):
coins = [1, 5, 10, 25]
dp = [0] * (M + 1)
dp[0] = 1
for coin in coins :
for i in range(coin, M + 1) :
dp[i] = (dp[i] + dp[i - coin])
return dp[M]
打家劫舍問(wèn)題
你是一個(gè)專業(yè)的小偷寸潦，計(jì)劃偷竊沿街的房屋。每間房?jī)?nèi)都藏有一定的現(xiàn)金社痛，影響你偷竊的唯一制約因素就是相鄰的房屋裝有相互連通的防盜系統(tǒng)见转，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統(tǒng)會(huì)自動(dòng)報(bào)警蒜哀。
給定一個(gè)代表每個(gè)房屋存放金額的非負(fù)整數(shù)數(shù)組斩箫，計(jì)算你 不觸動(dòng)警報(bào)裝置的情況下 ，一夜之內(nèi)能夠偷竊到的最高金額。
[分析]狀態(tài)轉(zhuǎn)移方程
數(shù)組個(gè)數(shù)length乘客，當(dāng)length=0時(shí)狐血，返回0
當(dāng)length=1時(shí)，dp[0]=nums[0]
當(dāng)length=2時(shí)易核，dp[1]=max(nums[0],nums[1])
當(dāng)length=3時(shí)匈织，dp[i]=max(dp[i-2]+nums[i],dp[i-1])
class Solution:
def rob(self, nums: List[int]) -> int:
length = len(nums)
if length == 0:
return 0
dp = [0]*length
dp[0]=nums[0]
if length > 1:
dp[1] = max(nums[0],nums[1])
if length > 2:
for i in range(2,length):
dp[i] = max(dp[i-2]+nums[i],dp[i-1])
return dp[-1]
目標(biāo)和
給定一個(gè)非負(fù)整數(shù)數(shù)組，a1, a2, ..., an, 和一個(gè)目標(biāo)數(shù)牡直，S∽贺埃現(xiàn)在你有兩個(gè)符號(hào) + 和 -。對(duì)于數(shù)組中的任意一個(gè)整數(shù)碰逸，你都可以從 + 或 -中選擇一個(gè)符號(hào)添加在前面乡小。
返回可以使最終數(shù)組和為目標(biāo)數(shù) S 的所有添加符號(hào)的方法數(shù)。
示例：
輸入：nums: [1, 1, 1, 1, 1], S: 3
輸出：5
解釋：
-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3
一共有5種方法讓最終目標(biāo)和為3花竞。
sum(P) 前面符號(hào)為+的集合劲件；sum(N) 前面符號(hào)為減號(hào)的集合，所以題目可以轉(zhuǎn)化為
因此題目轉(zhuǎn)化為01背包约急，也就是能組合成容量為sum(P)的方式有多少種
class Solution(object):
def findTargetSumWays(self, nums, S):
"""
:type nums: List[int]
:type S: int
:rtype: int
"""
w = (sum(nums) + S) // 2
if sum(nums) < S or (sum(nums) + S) % 2 == 1:
return 0
dp = [0] * (w+1)
dp[0] = 1
for num in nums:
j = w
while j >= num:
dp[j] += dp[j - num]
j -= 1
return dp[w]
組合總和 Ⅳ
給定一個(gè)由正整數(shù)組成且不存在重復(fù)數(shù)字的數(shù)組零远，找出和為給定目標(biāo)正整數(shù)的組合的個(gè)數(shù)。
示例:
nums = [1, 2, 3]
target = 4
所有可能的組合為：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
請(qǐng)注意厌蔽，順序不同的序列被視作不同的組合牵辣。
因此輸出為 7。
排列組合問(wèn)題首先想到貪心問(wèn)題奴饮，但這道題是明顯的動(dòng)態(tài)規(guī)劃問(wèn)題纬向，類似于上文中硬幣問(wèn)題。但與硬幣不同的是戴卜，順序不同的序列被視作不同的組合逾条。
class Solution:
def combinationSum4(self, nums: List[int], target: int) -> int:
dp = [0] * (target + 1)
dp[0] = 1
for i in range(target + 1) :
for num in nums :
if i >= num:
dp[i] += dp[i - num]
return dp[-1]
更多內(nèi)容，陸續(xù)補(bǔ)充
reference
希望用一種規(guī)律搞定背包問(wèn)題---Jackie1995
題目來(lái)源：力扣LeetCode,著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有投剥。
