数据结构与算法 / 技术文章

动态规划怎么找状态转移方程

推导动态规划时,先用一句话定义每个子问题,再问最后一步可以从哪里来。一个能运行的设计要写出状态、转移、初值、计算顺序和最终答案。这些信息应能说明每个候选为什么合法,以及是否漏掉了某种决策。

用最后一步找转移

例如每步只能爬 1 阶或 2 阶。定义 dp[i]dp[i] 为恰好到达第 ii 阶的方法数。最后一步来自第 i−1i-1 阶或第 i−2i-2 阶,两类路径互不重叠,因此对 i≥2i\ge2 有 dp[i]=dp[i−1]+dp[i−2]dp[i]=dp[i-1]+dp[i-2]。起点 dp[0]=1dp[0]=1 表示什么都不做的那一种路径,dp[1]=1dp[1]=1,答案为 dp[n]dp[n]。这些初值来自状态定义。斐波那契数列虽然递推式相同,但它的第零项为 0。

以哪个元素结尾,会影响后面能接什么

严格最长递增子序列不要求下标连续。令 dp[i]dp[i] 为以第 ii 个元素结尾的最长长度。若前一个元素在 j<ij<i,还须满足 a[j]<a[i]a[j]<a[i] 才能接上。只有一个元素也是合法子序列,所以:

dp[i]=max⁡({1}∪{dp[j]+1∣j<i, a[j]<a[i]})dp[i]=\max\left(\{1\}\cup\{dp[j]+1\mid j<i,\ a[j]<a[i]\}\right)

按 ii 从小到大计算。答案是所有 dp[i]dp[i] 的最大值,空数组为 0。用一个数字记录整个前缀的最优长度,通常不足以判断下一项能否接到那个前缀结果后面。保留结尾下标使转移能够检查实际的结尾元素。

0-1 背包的“选”和“不选”

令 dp[i][c]dp[i][c] 表示只考虑前 ii 件物品、总重量至多 cc 时的最大价值。第 ii 件物品重量为 wiw_i、价值为 viv_i。

  • 不选它,沿用 dp[i−1][c]dp[i-1][c]。
  • 只有 c≥wic\ge w_i 时才可选择它,候选值为 dp[i−1][c−wi]+vidp[i-1][c-w_i]+v_i。
  • 两种决策都合法时取最大值。第零行全为 0,因为可以一个也不选。

对非负整数容量和正整数重量,可以用一维数组保存上一层信息。每件物品处理时,容量应从大到小更新,使右侧较小容量仍来自上一层。从小到大会在同一轮重复使用该物品。例如只有一件重量 2、价值 3 的物品,容量 4 时正确结果仍是 3。若题目要求恰好装满,应将容量 0 以外的起始状态设为不可达,转移也只从可达状态出发。MIT 0-1 背包讲义

运行代码检查边界

python
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 背包的边界检查通过")

代码假定 nn 和容量是非负整数,背包重量是正整数。子序列的两层循环时间复杂度为 O(n2)O(n^2)。背包时间为 O(nC)O(nC),空间为 O(C)O(C),其中 CC 为容量数值。容量很大时,需先评估状态数量。

完成转移后,用空输入、最小非空输入、无法选择、恰好能选和重复元素做对照。如果一段历史会改变后续选择是否合法,就把会影响选择的部分加入状态。如果两段历史对后续的影响完全相同,就可以只保留对应的计数或最优值。将每种决策与依赖的较小状态对应起来,再决定按下标、容量或区间长度的哪种顺序计算。

目录与阅读设置

记录一个想法

动态规划怎么找状态转移方程

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通