跳转至

基本思想和使用条件

  • 基本思想：通过把原问题分解为相对简单的子问题的方式求解复杂问题
  • 使用条件：
    • 最优子结构
    • 无后效性
    • 子问题重叠

例

矩阵乘法：设 \(A_{1},A_{2},\dots,A_{n}\) 为矩阵序列， \(A_{i}\) 为 \(P_{i -1} \times P_{i}\) 阶矩阵， \(i = 1, 2, \dots,n\) 。确定乘法顺序使得元素相乘的总次数最少。

输入 \(P = <P_{0}, P_{1}, \dots,P_{n}>\), \(A_{i,j}\) 表示乘积 \(A_{i}A_{i + 1}\dots A_{j}\) 的结果，其最后一次相乘是

$$ A_{i, j} = A_{i, k} A_{k + 1, j} $$ \(m[i, j]\) 表示得到 \(A_{i, j}\) 的最少的相乘次数，递推方程：

\[ m[i,j] = \begin{cases} 0, i = j \\\ min_{i \leq k < j} \{m[i,k] + m[k + 1, j] + P_{i - 1}P_{k}P_{j}\}, i < j \end{cases} \]

递归实现：

def RecurMatrixChain(P, i, j):
    m = [[ 114514 for _ in range(j)] for _ in range(i)]
    s = [[ x for j in range(j)] for x in range(i)]
    for k in range(i, j-1):
        q = RecurMatrixChain(P, i, k) + RecurMatrixChain(P, k+1, j) + P[i-1] * P[k] * P[j]
        if q < m[i][j]:
            m[i][j] = q, s[i][j] = k
    return m[i][j]

复杂性满足递推关系：

\[ T(n) \geq \begin{cases} O(1), n = 1 \\\ \sum\limits_{k=1}^{n - 1} (T(k) + T(n - k) + O(1)), n > 1 \end{cases} \]
\[ T(n) \geq O(n) + \sum\limits_{k=1}^{n - 1} T(k) + \sum\limits_{k=1}^{n - 1} (n - k) = O(n) + 2 \sum\limits_{k=1}^{n - 1} T(k) \]

数学归纳法证明 \(T(n) \geq 2^{n - 1}\)

复杂性高的原因：子问题重复计算

迭代实现：

for (int r = 2; r <= n; r++) {
    for (int i = 1; i <= n - r + 1; i++) {
        int j = i + r - 1;
        m[i][j] = m[i + 1][j] + p[i - 1] * p[i] * p[j];
        s[i][j] = i;
        for (int k = i + 1; k <= j - 1; k++) {
            int t = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
            if (t < m[i][j]) {
                m[i][j] = t, s[i][j] = k;   
            }
        }   
    }
}

复杂性： \(O(n^{3})\)

两种算法的比较：

递归算法：复杂性高

非递归算法：复杂性较低

原因：

  1. 递归动态规划算法的子问题被多次重复计算
  2. 子问题计算次数呈指数级增长
  3. 非递归动态规划算法每个子问题只计算一次
  4. 子问题的计算随问题规模成多项式增长

动态规划算法设计步骤

  1. 将问题表示成多步判断，确定子问题的边界
    1. 整个判断序列就对应问题的最优解
    2. 每步判断对应一个子问题，子问题类型与原问题一样
  2. 确定优化函数，以函数的极大（或极小）作为判断的依据
  3. 确定是否满足优化原则——动态规划算法的必要条件
  4. 确定子问题的重叠性（降低复杂度）
  5. 列出关于优化函数的递推方程（或不等式）和边界条件
  6. 自底向上计算子问题的优化函数值
  7. 备忘录方法（表格）存储中间结果
  8. 设立标记函数求解问题的解

最长公共子序列（LCS）问题

int n, m, a[MAXN], b[MAXN], f[MAXN][MAXN];

int dp() {
    for (int i = 1; i < n=; i++)
        for (int j = 1; j <= m; j++) 
            if (a[i] == b[j])
                f[i][j] = f[i - 1][j - 1] + 1;
            else 
                f[i][j] = std::max(f[i - 1][j], f[i][j - 1]); 
    return f[n][m];
}