在分治算法中，我们已经知道要将一个问题分裂成不同的子问题来解决，但是，如果有些时候子问题之间存在覆盖问题，那么再利用 分治算法得到的时间复杂度就会非常大，所以，我们往往使用制表法来解决这个问题，中文名“动态规划”。
动态规划的解 （ OP, optimal）往往有很多个, 但是我们会用 value 进行标注这个 解，即我们可以通过比较 value 来找到最优解 (OTV, optimal value)。

从斐波那契讲起

如果我们要求解斐波那契数列中第 n 个数，那么我们可以用递归 (Top-Down) 的方法：

1
2
3
4
5
6
def fib(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fib(n-1) + fib(n-2)

但是这个方法的时间复杂度是 O(2n)O(2^n)，时间表达式 T(n)=T(n−1)+T(n−2)+O(1)T(n) = T(n-1) + T(n -2)+ O(1)
因为我们会重复计算很多次 fib(n-1) 和 fib(n-2)。
如果要解决这个重复计算的问题，我们可以联想到加入一个 memoization 的方法
即将每一个 算好的 fib 记录到 memo(n) 中

1
2
3
4
5
6
7
8
9
def fib(n, memo):
    if n == 0:
        return 0
    if n == 1:
        return 1
    if memo[n] != -1:
        return memo[n]
    memo[n] = fib(n-1, memo) + fib(n-2, memo)
    return memo[n]

这样我们就可以将时间复杂度降到 O(n)O(n)，因为我们只需要计算每个 fib 一次。但是这样的做法就不是那么直观了，尤其是在分析复杂度的时候，经常会有已经被审查过、删除掉的部分乱入，所以，我们可能需要一个正向的算法解决这个问题:

正向数组填写 Bottom-Up Table Filling

我们直接使用递推 iteration 思想，将一个数组进行从小到大填写

1
2
3
4
5
6
7
def fib(n):
    memo = [-1 for _ in range(n+1)]
    memo[0] = 1
    memo[1] = 1
    for i in range(2, n+1):
        memo[i] = memo[i-1] + memo[i-2]
    return memo[n]

这样我们就可以直接得到结果，而且时间复杂度是 O(n)O(n)，空间复杂度也是 O(n)O(n) 但是需要从递归的思考顺序转变到正向填写的顺序和逻辑

如何从递归到动态规划

  1. 将一个递归表达式的返回值变成一个 value
  2. 通过 bottom-up 的顺序计算递归返回值 (一般的递归是 top-down, 这里也侧面说明了 动态规划要求有序性)
  3. 找到需要的值并且返回

例子

假设你现在在给新学期排课程表，每门课有各自的学习价值，并且其长度、时间范围互相交错，如何选择一种课程总价值最高的排课程表呢？
首先我们将课程时间表按照结束时间进行排序 (有序化) 然后我们选择最后的一门课 JnJ_n, 这门课有选择和不选的两种情况，那么命运的齿轮开始转动，选择这门课的时候，我们向前找到最后一个不重叠的课程 JiJ_i, 这样我们就有新的时间表达式 OTV(J1⋯ ,Ji)+val(Jn)OTV(J_1\cdots, J_i) + val(J_n) ; 如果不选这门课，我们就有 OTV(J1⋯ ,Jn−1)OTV(J_1\cdots, J_{n-1})，这样我们就可以得到一个递归表达式：

OTV(J1⋯ ,Jn)=max⁡(OTV(J1⋯ ,Jn−1),OTV(J1⋯ ,Ji)+val(Jn))OTV(J_1\cdots, J_n) = \max(OTV(J_1\cdots, J_{n-1}), OTV(J_1\cdots, J_i) + val(J_n))

这是一个递归表达式，而且我们会发现其中 J1⋯JiJ_1\cdots J_i 部分会被重复计算，因此结合上述方法，我们可以正向填表计算 OTV(J1⋯Ji)OTV (J_1\cdots J_i) 这样不会重复计算了

典 · 最长递增子序列 LIS

这个是 力扣 的第一道困难的题目，运用动态规划算法可以很巧妙的解决这个问题
首先我们用递归去思考：我们选择或者不选最后一个数，这取决于这个数作为子序列的最后元素能不能大于现有的最长子序列

1
2
3
# max_list 表示现有的最长子序列长度
# new_list 表示能加入新元素的最长子序列长度(尚未加入)
max_len = 1 + max(max_list, new_list)

那么新问题就是，如何判断能不能插入新元素？我们需要知道在这个元素之前的最长的子序列长度，以及能容纳这个新元素的最长子序列长度，如果使用上述的递归式进行展开，很不巧的 max_list 很有可能会多次出现（覆盖），所以我们考虑用正向填表进行简化
我们用一个额外的数组 B[i]B[i] 来记载到 list[i]list[i] 元素（包含）的最长子序列长度，那么我们可以得到一个递推式:

1
2
3
4
5
6
B[0] = 0
B[1] = 1
for i in range(1, n):
    for j in range(i):
        if list[i] > list[j]:  # 新元素大于旧有元素
            B[i] = max(B[i], B[j] + 1)  # 找到最大可用子序列插入

时间复杂度 是 O(n2)O(n^2) 因为还是不可避免要比较任意两个的大小

典 · 最大共有子串 LCS

  1. 我们先考虑一种特殊情况，两个序列的末尾字符相同，我们先证明命题1：一定存在 LCS 包含两个序列 S1,S2S_1, S_2 的末尾字符
  2. 然后再证明命题2：对于拥有上述末尾相同的 S1S_1, S2S_2 字符串，那么 LCS 长度一定等于 LCS(S1[1⋯n−1]LCS(S_1[1\cdots n - 1], S2[1⋯m−1])+1S_2[1\cdots m - 1]) + 1
  3. 接下来我们需要解决 S1,S2S_1, S_2 末尾字符不相同的情况，我们可以得到一个递归表达式：

LCS(S1,S2)=max⁡(LCS(S1[1⋯n−1],S2),LCS(S1,S2[1⋯m−1]))LCS(S_1, S_2) = \max(LCS(S_1[1\cdots n-1], S_2), LCS(S_1, S_2[1\cdots m-1]))

这个就会出现很多的覆盖
最后我们还要找到 base case: 某一个字符串是 空的，那么 LCS 一定是 0

正向填表解决

这里由于要 两两 match，所以我们要用一个二维表进行存储
S1=GAC,S2=AGCATS_1 = GAC, S_2 = AGCAT

∅\varnothing A G C A T
∅\varnothing 0 0 0 0 0 0
G 0 0 1 1 1 1
A 0 1 1 1 2 2
C 0 1 1 2 2 2

原则：match 加左上角，不 match 继承左边或者上面的更大的，答案在右下角的

  • 左上角：左上角表明前面的已经被匹配的量都会汇集在此，例如上表的 C- C 匹配，左上角表示 AGAG 和 GAGA 的匹配最长为 1
  • 左边或者上面：看哪个字符串加上新元素的匹配长度更大
    时间复杂度 是 O(n⋅m)O(n\cdot m)