动态规划

概述

动态规划（dynamic programming）与分治方法相似，都是通过组合子问题的解来求解原问题（子问题的求解是递归进行的，将其划分为更小的子子问题）。

• 分治方法将问题划分为互不相交的子问题，递归地求解子问题，再将它们的解组合起来，求出原问题的解。
• 与之相反，动态规划应用于子问题重叠的情况，即不同的子问题具有公共的子子问题。在这种情况下，分治算法会做许多不必要的工作，它会反复地求解那些公共子子问题。而动态规划算法对每个子子问题只求解一次，将其解保存在一个表格中，从而无需每次求解一个子子问题时都重新计算，避免了这种不必要的计算工作。

所以形象地说：动态规划是有记忆的分治。

---

动态规划方法通常用来求解最优化问题(optimization problem) 。这类问题可以有很多可行解，每个解都有一个值，我们希望寻找具有最优值（最小值或最大值）的解。可能有多个解都达到最优值。

具体来说，动态规划问题一般具有一下两个性质：

• 最优子结构：一个问题的最优解包含其子问题的最优解。
• 重叠子问题：问题空间必须足够“小”，即问题的递归算法会反复地求解相同的子间题，而不是一直生成新的子问题。

---

我们通常按如下 4 个步骤来设计一个动态规划算法：

1. 刻画最优解的结构。
2. 给出最优解的值的递推公式。
3. 自底向上地计算最优解的值。
4. 利用计算出的信息构造一个最优解。

步骤 1~3 是动态规划算法求解问题的基础。

• 如果我们仅仅需要一个最优解的值，而非解本身，可以忽略步骤 4 。
• 如果需要一个最优解, 有时就需要在执行步骤 3 的过程中维护一些额外信息，以便用来构造一个最优解。

所以形象地说：动态规划就是一种“数学归纳法”。

---

实例

斐波那契数列

如果使用一般的分治算法（递归），会有大量的重复计算。以下图为例，计算 F₆ 的递归过程中 F₃ = F₂ + F₁ 被重复进行了 3 次。

def fibonacci(n):
    if n <= 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)

动态规划算法为了避免重复的子问题计算，把每次计算过的子问题的解都记录下来，以后在遇到相同子问题时，直接“背答案”。

def fibonacci_dp(n):
    if n <= 0:
        return 0
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

# Example usage:
n = 10
print(f"Fibonacci number at position {n} is: {fibonacci_dp(n)}")

---

钢条切割

问题描述：

给定一段长度为 n 英寸的钢条和一个价格表 p_i (i = l, 2, …, n)。求切割钢条方案，使得销售收益 r 最大。注意：如果长度为 n 英寸的钢条的价格 P_n 足够大，最优解可能就是完全不需要切割。

长度	1	2	3	4	5	6	7	8	9	10
价格	1	5	8	9	10	17	17	20	24	30

解决办法：

首先我们将这个问题描述数学化。

如果一个最优解将钢条切割为 k 段（0 < k < n+1）, 那么最优切割方案：

将钢条切割为长度分别为 i₁, i₂, …, i_k 的小段，得到最大收益：

考虑给出 r_n 的递推公式。

切割的第一刀，可以切在任何位置。且如果是最优解，则切后的两段钢条的切割方案也一定是最优解。

def cut_rod(p, n):
    # p 是价格列表，n 是钢条的长度
    r = [0] * (n + 1)

    for j in range(1, n + 1):
        max_val = float('-inf')
        for i in range(0, j + 1):
            # 计算切割后的最大收益
            max_val = max(max_val, p[i] + r[j - i])
        r[j] = max(max_val, p[j])

    return r[n]


# 价格表 & 钢条长度
prices = [0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30]
length = 10

# 计算最大收益
max_profit = cut_rod(prices, length)
print(f"最大收益为: {max_profit}")

---

矩阵链乘法

问题描述：

给定一个 n 个矩阵的序列（矩阵链）<A₁, A₂, …, A_n >，且矩阵 A_i 的规模为 p_i-1 *p_i 。求完全括号化方案（使用结合律加括号），使乘积 A₁A₂…A_n 所需标量乘法次数最少。

解决办法：

首先：用子问题的最优解来递归地定义原问题最优解。

对矩阵链乘法问题，我们可以这么定义子问题：

• 对所有 1 <= i <= j <= n ，确定 <A_i, A_i+1, …, A_j > 的最小代价括化方案。

• 令 m[i, j] 表示计算矩阵 A_i A_i+1 … A_j 所需标量乘法次数的最小值，那么，原问题的最优解计算 A₁A₂…A_n 所需的最低代价就是m[1, n]。

然后不难得出m[i, j]的递推公式：

m[i, j] 的值给出了子问题最优解，但它并未提供足够的信息来构造最优解。为此，我们用 s[i, j] 保存 A_i A_i+1 … A_j 最优括号化方案的分割点位置k。

def matrix_chain_order(p):
    # 矩阵的数量，p 是矩阵的维度列表
    # 创建一个二维数组 m，其中 m[i][j] 表示计算矩阵 Ai...Aj 的乘积所需的最小标量乘法次数
    # 创建一个二维数组 s，其中 s[i][j] 存储计算 m[i][j] 时最优分割点 k 的位置
    n = len(p) - 1
    m = [[0] * n for _ in range(n)]
    s = [[0] * n for _ in range(n)]
    
    # 按链的长度 l 进行处理，l 从 2 到 n
    for l in range(2, n + 1):
        for i in range(n - l + 1):
            j = i + l - 1
            m[i][j] = float('inf')
            for k in range(i, j):
                # q 表示 Ai...Ak 和 Ak+1...Aj 的乘积所需的标量乘法次数
                q = m[i][k] + m[k+1][j] + p[i] * p[k+1] * p[j+1]
                if q < m[i][j]:
                    m[i][j] = q
                    s[i][j] = k
    return m, s

def print_optimal_parens(s, i, j):
    if i == j:
        print(f'A{i+1}', end='')
    else:
        print('(', end='')
        print_optimal_parens(s, i, s[i][j])
        print_optimal_parens(s, s[i][j] + 1, j)
        print(')', end='')

# 矩阵的维度列表，例如：30*35、35*15、15*5、5*10、10*20、20*25
p = [30, 35, 15, 5, 10, 20, 25]
m, s = matrix_chain_order(p)
print("最少的标量乘法次数是:", m[0][len(p) - 2])
print("最优乘法顺序是:", end=' ')
print_optimal_parens(s, 0, len(p) - 2)

---

最长公共子序列

问题描述：

给定两个序列 X = <x₁, x₂, …, x_m> 和 Y = <y₁, y₂, …, y_n>，求 X 和 Y 最长的公共子序列。

解决办法：

首先，观察到最长公共子序列的递归结构。

我们定义 c[i,j] 表示 X_i 和 Y_j 的最长公共子序列的长度。

则不难得到递推公式：

def lcs(X, Y):
    # 初始化矩阵
    m = len(X)
    n = len(Y)
    c = [[0] * (n + 1) for _ in range(m + 1)]

    # 构建c矩阵
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if X[i - 1] == Y[j - 1]:
                c[i][j] = c[i - 1][j - 1] + 1
            else:
                c[i][j] = max(c[i - 1][j], c[i][j - 1])

    # 从c矩阵回溯找到LCS
    index = c[m][n]
    lcs_seq = [""] * (index)

    # 回溯找LCS
    i, j = m, n
    while i > 0 and j > 0:
        if X[i - 1] == Y[j - 1]:
            lcs_seq[index - 1] = X[i - 1]
            i -= 1
            j -= 1
            index -= 1
        elif c[i - 1][j] > c[i][j - 1]:
            i -= 1
        else:
            j -= 1

    return "".join(lcs_seq)

# 测试
X = "ABCBDAB"
Y = "BDCAB"
print(f"LCS of {X} and {Y} is {lcs(X, Y)}")