动态规划 · Learning Notes

动态规划把问题拆成子问题，保存每个子问题的答案，再按依赖顺序复用，避免同一状态被反复计算。它适用于子问题大量重叠、且原问题最优解由子问题最优解构成的问题。本页用最长递增子序列和0/1背包说明状态、转移、边界和方案还原的写法。子问题互不重叠时，分解方式见分治法；记忆化仍然借助递归的调用与返回。

定义

动态规划把原问题拆成若干子问题，为每个子问题定义状态并保存其答案，再按依赖顺序用子问题的答案计算当前状态。

一个动态规划方案包含四部分：

状态：用一个或一组变量描述子问题，例如a[i][j] 表示“前i件物品、容量为j时的最大价值”。
转移：当前状态由哪些更小状态、按什么规则得到。
边界：最小子问题的答案，例如没有物品或容量为0时价值为0。
计算顺序：保证计算当前状态时，它依赖的状态已经算好。

同样的状态和转移可以用两种方式实现：自底向上按顺序填表，或自顶向下递归并缓存结果（记忆化）。

性质

适用条件

重叠子问题：不同的计算路径会反复遇到同一个子问题。若子问题互不重叠，分治就够了，保存答案不会减少工作量。
最优子结构：原问题的最优解可以由子问题的最优解组合得到。
无后效性：状态一旦确定，后续计算只依赖这个状态，不依赖到达它的具体路径。状态设计必须把影响后续选择的信息都包含进去。

自底向上与记忆化

写法	计算方式	优点	代价
自底向上	按依赖顺序填表	无递归调用开销，便于控制空间	必须先确定计算顺序，可能计算用不到的状态
记忆化	递归求解，查表命中直接返回	只计算真正需要的状态，形式贴近递推式	有调用栈深度限制，函数调用有额外开销

两种写法使用同一组状态和转移，时间复杂度通常相同，差别在常数、空间和实现难度。

与分治、贪心的对比

动态规划与分治都拆子问题，区别是动态规划保存并复用子问题的答案；与贪心的区别是动态规划会比较多个候选，不提前固定一个选择。判断顺序可以是：子问题重叠就考虑动态规划；能证明局部最优可扩展到全局最优就用贪心；子问题独立且合并代价可控就用分治。

设计步骤

定义状态

用一个明确的量回答“子问题是什么”，写清下标的含义和取值范围。
写出转移

枚举当前状态的最后一步，把它化成一个或几个更小状态，并说明取最大、最小还是求和。
确定边界

写出最小规模下的答案，检查转移在边界处不会越界。
确定顺序

让转移依赖的状态先被计算；自底向上时通常按下标从小到大填表。
还原方案

若题目要求具体方案而不只是最优值，另开一个数组记录每个状态的选择，最后从终点回溯。

代价

状态数为 $N$ 、每个状态转移检查 $K$ 个候选时，时间为 $O(NK)$ ，空间为 $O(N)$ （或按需压缩）。背包的二维表有 $(n+1)(m+1)$ 个状态；最长递增子序列的Asc有 $n$ 个状态，每个状态扫描它前面的所有元素，因此是 $O(n^2)$ 。

例子

最长递增子序列：按结尾元素定义状态

最长递增子序列要求从列表中按原顺序取出一个子序列，使数值严格递增，并让长度最大。子序列不要求元素在列表中相邻。

1
def LIS(L):
2
    Asc = [1] * len(L)
3
    Tra = [-1] * len(L)
4
    # Asc[i] 存放以L[i]结尾的最长递增子序列长度。
5
    # Tra[i] 存这个子序列中L[i]的前一个元素下标，用于还原序列。
6
    for i in range(1, len(L)):
7
        X = []
8
        for j in range(0, i):
9
            if L[i] > L[j]:
10
                X.append(j)
11
        for k in X:
12
            if Asc[i] < Asc[k] + 1:
13
                Asc[i] = Asc[k] + 1
14
                Tra[i] = k
15
    print("Asc:", Asc)
16
    print("Tra:", Tra)
17
    best = 0
18
    for i in range(1, len(Asc)):
19
        if Asc[i] > Asc[best]:
20
            best = i
21
    print("最长递增子序列的长度是", Asc[best])
22

23
    X = [L[best]]
24
    i = best
25
    while Tra[i] >= 0:
26
        X = [L[Tra[i]]] + X
27
        i = Tra[i]
28
    print("最长递增子数列=", X)
29

30

31
L = [5, 2, 4, 7, 6, 3, 8, 9]
32
LIS(L)

状态Asc[i] 表示“以L[i] 结尾”的最长递增子序列长度，边界是每个元素单独构成子序列时的长度1。转移检查所有j < i且L[j] < L[i] 的前驱，取Asc[j] + 1的最大值。Tra[i] 记录取得最大值的那个j，最后从最长长度所在的下标向前回溯，就能得到具体序列。

对L = [5, 2, 4, 7, 6, 3, 8, 9]，程序输出Asc为 [1, 1, 2, 3, 3, 2, 4, 5]，最大长度为5；按Tra回溯得到 [2, 4, 7, 8, 9]。长度为5的递增子序列不唯一，[2, 4, 6, 8, 9] 同样合法，但Tra在长度相同的候选中保留了先遇到的下标，所以这段代码还原的是前者。

同一问题的直接递归写法

不保存答案，直接按定义展开，也能写出同一个状态：

1
def Asc(k):
2
    if k == 0:
3
        return 1
4
    X = []
5
    for i in range(0, k):
6
        if L[k] > L[i]:
7
            X.append(Asc(i))
8
    if len(X) > 0:
9
        return max(X) + 1
10
    else:
11
        return 1
12

13

14
def LIS_R(L):
15
    X = []
16
    for k in range(0, len(L)):
17
        X.append(Asc(k))
18
    print(X)
19
    print(max(X))
20

21

22
L = [5, 2, 4, 7, 6, 3, 8, 9]
23
LIS_R(L)

Asc(k) 的含义与动态规划版完全相同，但每次调用都重新展开所有更小的下标。以递增列表为例，Asc(k) 会调用Asc(0) 到Asc(k-1)，调用次数满足 $T(k)=1+\sum_{i<k}T(i)$ ，随规模指数增长；同一个Asc(i) 被不同上层反复计算。

把算过的Asc(i) 存进一张表，递归再次遇到时直接返回，每个状态只计算一次；状态有 $n$ 个，每个状态最多检查 $n$ 个前驱，总时间为 $O(n^2)$ 。这正是自顶向下的动态规划，也就是记忆化。

0/1背包：递归写法

有n件物品，第i件重量为w[i]、价值为v[i]，背包容量为j。每件物品要么整件放入，要么不放，不能重复使用。

1
w = [0, 4, 5, 2, 1, 6]
2
v = [0, 45, 57, 22, 11, 67]
3
n = len(w) - 1
4
j = 8
5
x = [False for raw in range(n + 1)]
6

7

8
def knap_r(n, j):
9
    if (n == 0) or (j == 0):
10
        x[n] = False
11
        return 0
12
    elif (j >= w[n]) and (knap_r(n - 1, j - w[n]) + v[n] > knap_r(n - 1, j)):
13
        x[n] = True
14
        return knap_r(n - 1, j - w[n]) + v[n]
15
    else:
16
        x[n] = False
17
        return knap_r(n - 1, j)
18

19

20
print("最大价值为：", knap_r(n, j))
21
print("物品的装入情况为：", x[1:])

knap_r(n, j) 表示“只考虑前n件物品、容量为j时的最大价值”。若第n件能放下，就比较“放入它”和“不放入它”两种结果，取较大者；否则只能不放。

问题在于，比较两个分支时每一支都会再次递归，knap_r(n-1, j-w[n]) 和knap_r(n-1, j) 内部又共享大量更小的子问题。同一个 (n, j) 被重复求解，调用次数随物品数指数增长。

0/1背包：自底向上填表

把“前i件物品、容量j”的全部组合列成二维表，按i从小到大、j从小到大填写，每个状态只算一次。

1
w = [0, 4, 5, 2, 1, 6]
2
v = [0, 45, 57, 22, 11, 67]
3
n = len(w) - 1
4
m = 8
5
x = [False for raw in range(n + 1)]
6
a = [[0 for col in range(m + 1)] for raw in range(n + 1)]
7

8

9
def knap_DP(n, m):
10
    for i in range(1, n + 1):
11
        for j in range(1, m + 1):
12
            a[i][j] = a[i - 1][j]
13
            if (j >= w[i]) and (a[i - 1][j - w[i]] + v[i] > a[i - 1][j]):
14
                a[i][j] = a[i - 1][j - w[i]] + v[i]
15

16
    j = m
17
    for i in range(n, 0, -1):
18
        if a[i][j] > a[i - 1][j]:
19
            x[i] = True
20
            j = j - w[i]
21
    return a[n][m]
22

23

24
print("最大价值为：", knap_DP(n, m))
25
print("物品的装入情况为：", x[1:])

a[i][j] 的转移分两种情形：容量j放不下第i件物品时，价值只能继承a[i-1][j]；放得下时，在“不放”与“放”之间取较大值：

a[i][j]=\max\bigl(a[i-1][j],\ a[i-1][j-w[i]]+v[i]\bigr),\qquad j\ge w[i].

边界是a[0][j] = 0和a[i][0] = 0。填表完成后，从a[n][m] 向前回溯：若a[i][j] > a[i-1][j]，说明第i件物品被放入，把j减去它的重量；否则这件物品没有放入。

对给定的重量、价值和容量8，最大价值为90，装入的是第2、3、4件物品，重量 $5+2+1=8$ 。时间复杂度为 $O(nm)$ ，空间为 $O(nm)$ 。

交互探索

查看找零问题中每个金额的最优结果，比较当前状态与它的前驱状态。

较小金额的结果怎样组成最优解？

查看不同金额所需的最少硬币数及其状态转移。