1. 理論基礎

動態規劃是一種用空間換時間的方法，

如果需要重復計算某個數，就把它記下來，以避免重復運算。——by 左神

適用范圍：結果僅與狀態有關，與達到該狀態的路徑無關。
注：之所以有這個使用范圍限制，是因為 dp 表僅記錄狀態信息，沒有記錄是如何達到該狀態的。

解題步驟：
【1】問題拆解。看問題是否能拆解成若干子問題。
【2】定義狀態。確定 dp 表的維度。
【3】確定狀態轉移方式。這裡要做到不遺漏，找到每一條達到該狀態的路徑。
【4】確定初始狀態。根據狀態轉移方式，確定所需的初始狀態。

（以上，略去教科書上的概念，寫寫我自己的理解，如有不准確的地方請大佬們指正）

2. 0-1 背包問題

變量說明：
背包容量為 bag
物品共有 num 個
物品的重量為 weights ：[w_0,w_1,…,w_num-1]
物品的價值為 values：[v_0,v_1,…,v_num-1]

2.1 二維 dp 表

定義 dp[item][w] 為 當背包容量為 w 時，考慮前 item 項物品，背包所裝物品的最大價值。
因此，dp[item] 的價值，與 dp[item-1] 的價值相關。
首先要判斷 第 item 號物品是否能夠裝入當前背包，如果可以，則在 dp[item-1] 的基礎上得到 dp[item] 的路徑有兩條：

• 選擇裝第 item 項物品
  d p [ i t e m ] [ w ] = d p [ i t e m − 1 ] [ w − w e i g h t s [ i t e m ] ] + v a l u e s [ i t e m ] dp[item][w] = dp[item - 1][w - weights[item]] + values[item] dp[item][w]=dp[item−1][w−weights[item]]+values[item]
• 選擇不裝第 item 項物品
  d p [ i t e m ] [ w ] = d p [ i t e m − 1 ] [ w ] dp[item][w] = dp[item - 1][w] dp[item][w]=dp[item−1][w]

def bagTwoDe(bag, weights, values):
""" 關於第 item 號物品 不裝: dp[item][w] = dp[item - 1][w] 裝: dp[item][w] = dp[item - 1][w - weights[item]] + values[item] 發現可以做一些空間優化 """
num = len(weights)
dp = [[0] * (bag + 1) for _ in range(num)]
for item in range(num):
for b in range(1, bag + 1):
if weights[item] > b:
dp[item][b] = dp[item - 1][b]
else:
dp[item][b] = max(dp[item - 1][b - weights[item]] + values[item], dp[item - 1][b])
return dp[-1][-1]

寫一個測試用的例子

if __name__ == '__main__':
bag = 4
weights = [1, 4, 3]
values = [10, 30, 25]
a = bagTwoDe(bag, weights, values)
print(a)

2.2一維 dp 表

其實可以發現如果把dp[item- 1]那一層拷貝到dp[item]上，表達式完全可以是：dp[item][w] = max(dp[item][w], dp[item[w - weights[item]] + values[item])；因此，dp 表僅需要最後一行就可以了。代碼如下

def bagOneDe(bag, weights, values):
""" 用一維數組存儲時，背包重量應該倒序遍歷，防止需要的數值被修改 """
nums = len(weights)
dp = [0] * (bag + 1)
for item in range(nums):
for b in range( bag,-1,-1):
if weights[item] <= b:
dp[b] = max(dp[b], dp[b - weights[item]] + values[item])
return dp[-1]

if __name__ == '__main__':
bag = 4
weights = [1, 4, 3]
values = [10, 30, 25]
b = bagOneDe(bag, weights, values)
print(b)

3. Leetcode 上關於0-1背包的題目

416 分割等和子集

class Solution:
def canPartition(self, nums: List[int]) -> bool:
target = sum(nums) / 2
if int(target) != target:
return False
else:
target=int(target)
n=len(nums)
# col range(0,target)
# row range(0,n)
dp=[0]*(target+1)
for item in nums:
for w in range(target,-1,-1):
if item<=w:
dp[w]=max(dp[w],dp[w-item]+item)
if dp[-1]==target:
return True
else:
return False

1049. 最後一塊石頭的重量 II

class Solution:
def lastStoneWeightII(self, stones: List[int]) -> int:
# 0-1 bag
stonesum = sum(stones)
target = stonesum >> 1
dp = [0] * (target + 1)
for i in stones:
for j in range(target, -1, -1):
if i <= j:
dp[j] = max(dp[j], dp[j - i] + i)
return stonesum-2*dp[-1]