动态规划
背包DP
0-1背包
1
2
3
4
5
6
7
8
9def knapsack(capacity, weights, values):
dp = [0] * (capacity + 1)
for i in range(len(weights)):
weight = weights[i]
value = values[i]
# 倒序遍历确保每个物品只选一次
for j in range(capacity, weight - 1, -1):
dp[j] = max(dp[j], dp[j - weight] + value)
return dp[-1]多重背包
1
2
3
4
5
6
7
8
9
10
11
12def knapsack_multiple(capacity, weights, values, counts):
dp = [0] * (capacity + 1)
for i in range(len(weights)):
weight = weights[i]
value = values[i]
count = counts[i]
for j in range(capacity, weight - 1, -1):
for k in range(1, count + 1):
if weight * k > j:
break
dp[j] = max(dp[j], dp[j - weight * k] + value * k)
return dp[-1]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18def knapsack_multiple(capacity, weights, values, counts):
dp = [0] * (capacity + 1)
for i in range(len(weights)):
weight = weights[i]
value = values[i]
count = counts[i]
k = 1
while k < count:
# 二进制拆分：将当前k个物品视为01背包的子物品
for j in range(capacity, weight * k - 1, -1):
dp[j] = max(dp[j], dp[j - weight * k] + value * k)
count -= k
k *= 2
# 处理剩余无法拆分的cnt个物品
if count > 0:
for j in range(capacity, weight * count - 1, -1):
dp[j] = max(dp[j], dp[j - weight * count] + value * count)
return dp[-1]完全背包
1
2
3
4
5
6
7
8
9def knapsack_complete(capacity, weights, values):
dp = [0] * (capacity + 1)
for i in range(len(weights)):
weight = weights[i]
value = values[i]
# 正序遍历允许重复选择当前物品
for j in range(weight, capacity + 1):
dp[j] = max(dp[j], dp[j - weight] + value)混合背包
通过组合0-1背包、多重背包和完全背包实现状态压缩
capacity和weights除以最大公约数作为新的容量和重量。
区间DP
树形DP
- 树上背包
1
2
3
4
5
6
7
8
9
10
11
12
13def dfs(i):
weight = weights[i]
value = values[i]
dp = [0] * (capacity + 1)
for w in range(weight, capacity + 1):
dp[w] = value
for child in children[i]:
child_dp = dfs(child)
for j in range(capacity, weight - 1, -1):
for k in range(j - weight + 1):
dp[j] = max(dp[j], dp[j - k] + child_dp[k])
return dp
状压DP
数位DP
DP优化
经典问题
- 鸡蛋掉落
f(k, n)表示有k个鸡蛋、n层楼时，最坏情况下的最小尝试次数。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36def superEggDrop(self, k: int, n: int) -> int:
cache = dict()
def dp(k, n):
if n == 0:
return 0
if k == 1:
return n
item = (k, n)
if item in cache:
return cache[item]
left = 1
right = n
while left + 1 < right:
mid = (left + right) // 2
broken = dp(k - 1, mid - 1)
not_broken = dp(k, n - mid)
if broken == not_broken:
left = mid
right = mid
else:
if broken > not_broken:
right = mid
else:
left = mid
res = n
for x in range(left, right + 1):
res = min(res, 1 + max(dp(k - 1, x - 1), dp(k, n - x)))
cache[item] = res
return res
return dp(k, n)