数据结构与算法 / 技术文章
动态规划怎么找状态转移方程
推导动态规划时,先用一句话定义每个子问题,再问最后一步可以从哪里来。一个能运行的设计要写出状态、转移、初值、计算顺序和最终答案。这些信息应能说明每个候选为什么合法,以及是否漏掉了某种决策。
用最后一步找转移
例如每步只能爬 1 阶或 2 阶。定义 为恰好到达第 阶的方法数。最后一步来自第 阶或第 阶,两类路径互不重叠,因此对 有 。起点 表示什么都不做的那一种路径,,答案为 。这些初值来自状态定义。斐波那契数列虽然递推式相同,但它的第零项为 0。
以哪个元素结尾,会影响后面能接什么
严格最长递增子序列不要求下标连续。令 为以第 个元素结尾的最长长度。若前一个元素在 ,还须满足 才能接上。只有一个元素也是合法子序列,所以:
按 从小到大计算。答案是所有 的最大值,空数组为 0。用一个数字记录整个前缀的最优长度,通常不足以判断下一项能否接到那个前缀结果后面。保留结尾下标使转移能够检查实际的结尾元素。
0-1 背包的“选”和“不选”
令 表示只考虑前 件物品、总重量至多 时的最大价值。第 件物品重量为 、价值为 。
- 不选它,沿用 。
- 只有 时才可选择它,候选值为 。
- 两种决策都合法时取最大值。第零行全为 0,因为可以一个也不选。
对非负整数容量和正整数重量,可以用一维数组保存上一层信息。每件物品处理时,容量应从大到小更新,使右侧较小容量仍来自上一层。从小到大会在同一轮重复使用该物品。例如只有一件重量 2、价值 3 的物品,容量 4 时正确结果仍是 3。若题目要求恰好装满,应将容量 0 以外的起始状态设为不可达,转移也只从可达状态出发。MIT 0-1 背包讲义
运行代码检查边界
def fibonacci(n):
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a
def lis_length(values):
lengths = [1] * len(values)
for i, value in enumerate(values):
for j in range(i):
if values[j] < value:
lengths[i] = max(lengths[i], lengths[j] + 1)
return max(lengths, default=0)
def knapsack(items, capacity):
best = [0] * (capacity + 1)
for weight, value in items:
for remaining in range(capacity, weight - 1, -1):
best[remaining] = max(best[remaining], best[remaining-weight] + value)
return best[capacity]
assert fibonacci(0) == 0 and fibonacci(10) == 55
assert lis_length([]) == 0 and lis_length([2, 2, 2]) == 1
assert lis_length([3, 1, 2, 2, 4]) == 3
assert knapsack([(2, 3)], 4) == 3
assert knapsack([(5, 9)], 4) == 0
assert knapsack([(2, 3), (3, 4), (4, 5)], 5) == 7
print("斐波那契、严格递增子序列、0-1 背包的边界检查通过")代码假定 和容量是非负整数,背包重量是正整数。子序列的两层循环时间复杂度为 。背包时间为 ,空间为 ,其中 为容量数值。容量很大时,需先评估状态数量。
完成转移后,用空输入、最小非空输入、无法选择、恰好能选和重复元素做对照。如果一段历史会改变后续选择是否合法,就把会影响选择的部分加入状态。如果两段历史对后续的影响完全相同,就可以只保留对应的计数或最优值。将每种决策与依赖的较小状态对应起来,再决定按下标、容量或区间长度的哪种顺序计算。