算法基础 6 - 动态规划 Dynamic Programming

将一个复杂的问题，转化为可以递归的子问题，尽可能减少解的可能空间，然后进行局部暴力破解。

DP的特性与步骤（SRTBOT）

• 定义子问题（subproblem）
  • 使用词汇语句来描述子问题
  • 通常采用输入的子集：前缀、后缀、子串
  • 通常会采用额外的辅助变量对子问题进行扩充
• 关联性（Relate）
  • 子问题的求解通过递归来实现，$x(i)=f(x(j),\ \dots)$
• 拓扑顺序（Topological Order）
  • 问题的求解时单向递进的，不存在循环的回路
• 基本案列（Basic Cases）
  • 不存在关联性的初始状态的解
• 原始问题（Original Problem）
  • 展示如何由子问题求解原始问题

• 时间分析（Time Analysis）

  • 求解原始问题所需求解的所有子问题时间总和

    $$\sum_{x\in X}work(x),\ or |X|\cdot O(W)\quad if \ work(x)=O(W)$$

---

Trick 1: 增加记忆 - 斐波那契数

💡 通过存储子问题的解，提高递归求解的效率

问题：计算第n个斐波那契数$F_n$

DP求解：

• 子问题：计算第i个斐波那契数$F(i),\ i\in\{1, 2, \dots, n\}$
• 关联性：$F(i)=F(i-1)+F(i-2)$
• 拓扑顺序：递增 i
• 基本案例：$F(0)=0,\ F(1)=1$
• 原始问题：$F_n = F(n)$
• 时间分析：

$$T(n)=T(n-1)+T(n-2)+O(1)\to T = n\cdot O(1) = O(n)\ (by\ memo)$$

def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

def fib(n):
    memo = {}

    def F(i):
        if i < 2:
            return i
        if i not in memo:
            memo[i] = F(i - 1) + F(i - 2)
        return memo[i]

    return F(n)

Trick 2: 局部暴力破解 - 保龄球问题

💡 局部遍历问题所有可能解，通过子问题递归减少解集空间

问题：在一组给定带标签的保龄球数列，计算最大得分

• 每次可以击中一个或相邻两个保龄球，也可以选择不击球（结束）
• 击中一个得该球分数，击中相邻讲个得两球得分乘积
• 测试案例：$[-1,1,1,1,9,9,3,-3,-5,2,2]$

DP求解：

• 子问题：求解输入的子序列的最大得分B(i) = Max Score of Input v[i:n]
• 关联性（局部暴力破解）：B(i) = max{B(i+1), B(i+1)+v[i], B(i+2)+v[i]*v[i+1]}
• 拓扑顺序：递减 i (for i = n, n-1, 0)
• 基本案例：B(n) = B(n+1) = 0
• 原始问题：B(0)
• 时间分析：Time = O(n) subproblems * O(1) work on each = O(n)

def bowl(v):
    memo = {}

    def B(i):
        if i >= len(v)-1:
            return 0
        if i not in memo:
            memo[i] = max(B(i+1), B(i+1)+v[i], B(i+2)+v[i]*v[i+1])
        return memo[i]

    return B(0)

Trick 3: 通过子序列构造子问题 - 最长相同子序列（Longest Common Subsequence, LCS）

💡 通过输入的子序列（前缀、后缀、子串）构造子问题，再进行局部破解

问题：给定两个字符串，找出两个字符串最长的公共部分

• 测试案例：A = hieroglyphology, B = michaelangelo
• 解集：hello, heglo, iello, ieglo

DP求解：

• 子问题：x(i,j) = Longest Common Subsequence of A[i:n] and B[j:n]
• 关联性（局部暴力破解）:

$$x(i, j)= \begin{cases}x(i+1, j+1)+1 & \text { if } A[i]=B[j] \\ \max \{x(i+1, j), x(i, j+1)\} & \text { otherwise }\end{cases}$$

• 拓扑顺序：递减 i + j；先递减 i，然后递减 j
• 基本案例：x(i,|B|) = x(|A|,j) = 0
• 原始问题：x(0,0)
• 时间分析：Time = O(|A|+1)*O(|B|+1) subproblems * O(1) work on each = O(|A|*|B|)

def lcs(A, B):
    a, b = len(A), len(B)
    x = [[0]*(b+1) for _ in range(a+1)]
    for i in reversed(range(a)):
        for j in reversed(range(b)):
            if A[i] == B[j]:
                x[i][j] = x[i+1][j+1] + 1
            else:
                x[i][j] = max(x[i+1][j], x[i][j+1])
    return x[0][0]

Trick 4: 增加问题约束 - 最长递增子序列（Longest Increasing Subsequence, LIS）

💡 通过增加额外的约束条件修改原问题，降低子问题的解空间维度，提高局部暴力破解的效率

问题：给定一个字符串，找出最长的严格递增的子串

• 测试案例：A = carbohydrate
• 解集：abort

DP求解：

• 子问题：包含首个元素的最长递增子序列
  x(i) = Longest Increasing Subsequence of A[i:n] that include A[i]
• 关联性（局部暴力破解）:

$$x(i)=\max \{1+x(j)|i<j<| A \mid, A[j]>A[i]\} \cup\{1\}$$

• 拓扑顺序：递减 i
• 基本案例：x(n) = 1
• 原始问题：max(x(i)| 0 <= i <= |A|)
• 时间分析：Time = O(|A|) subproblems * O(log|A|) each by AVL Tree = O(|A|log|A|)

def lis(A):
    a = len(A)
    x = [1] * a
    for i in reversed(range(a)):
        for j in range(i, a):
            if A[j] > A[i]:
                x[i] = max(x[i], 1 + x[j])
    return max(x)

Trick 5: 子问题扩张 - 括号化算数运算（Arithmetic Parenthesization）

💡 将原问题扩张为几个**相关联的、并列的**子问题，对每个子问题采用局部暴力破解

问题：给定一个算数表达式$a_0 _1 a_1 _2 a_2 \cdots *_{n-1} a_{n-1}$，通过添加括号使运算结果最大化

• $*_i \in\{+, \times\}$，$a_i$为正、负整数
• 测试案例：$7+(-4) \times 3+(-5)$
• 解集：$((7)+((-4) \times((3)+(-5))))=15$

DP求解：

• 子问题：求解输入的子序列的最大和最小运算结果
  • x(i,j,opt) = opt value of subsquence $a_i_{i+1}\cdots_{j-1}a_{j-1}$
  • 0 ≤ i < j ≤ n, opt in {max, min}
• 关联性（局部暴力破解）：

$$\left.x(i, j, \text { opt })=\operatorname{opt}\left\{x\left(i, k, \text { opt }^{\prime}\right) *_k x\left(k, j, \text { opt }^{\prime \prime}\right)\right) \mid i<k<j ; \text { opt }^{\prime}, \mathrm{opt}^{\prime \prime} \in\{\min , \max \}\right\}$$

• 拓扑顺序：递增 j - i
• 基本案例：x(i,i+1,opt) = A[i]
• 原始问题：x(0,n,max)
• 时间分析：Time = O(n^2) subproblems * O(n) work on each = O(n^3)

def ap(A, O):
    a = len(A)
    a_max = [[0] * (a) for _ in range(a)]
    a_min = [[0] * (a) for _ in range(a)]

    def maxmin_subseq(i, k, j, opt):
        if O[k] == '*':
            a = [x*y for x in [a_max[i][k], a_min[i][k]] 
                 for y in [a_max[k+1][j], a_min[k+1][j]]]
        else:
            a = [x+y for x in [a_max[i][k], a_min[i][k]] 
                 for y in [a_max[k+1][j], a_min[k+1][j]]]
        if opt == "max":
            return max(a_max[i][j], max(a))
        else:
            return min(a_min[i][j], min(a))

    for i in reversed(range(a)):
        for j in range(i, a):
            if j == i:
                a_max[i][i] = A[i]
                a_min[i][i] = A[i]
            else:
                for k in range(i, j):
                    a_max[i][j] = maxmin_subseq(i, k, j, "max")
                    a_min[i][j] = maxmin_subseq(i, k, j, "min")

    return a_max[0][len(A)-1]