跳转至

动态规划

动态规划 (Dynamic Programming, DP) 算法是一种利用子问题的解来求解原问题的解的策略。通过实时存储子问题的解，该算法在原问题有大量「重叠子问题」的情况下尤为有效。

当然，动态规划算法奏效的前提是原问题具有「最优子结构」的性质，即原问题可以被分解为多个子问题来求解；同时，动态规划算法还需要遵守「无后效性」原则，即当前问题依赖的子问题只能是已经被解决的问题，而不能是在未来才会被解决的问题。推荐阅读《动态规划杂谈》 1 来对动态规划有一个更深刻的认知。

从上面的文字可以看出，动态规划算法是基于子问题得到原问题的解，这个过程一般被称为状态转移。常见的有「被动转移」与「主动转移」两种策略，但这仅仅是思考习惯的区别，本文将会全部使用前者。下图展示了两种转移策略的逻辑：

被动转移 vs. 主动转移

被动转移 vs. 主动转移

动态规划算法的核心有两点：

  1. 状态定义。如何合理定义做到「完整表示」所有状态？
  2. 状态转移。如何合理划分做到「不重不漏」更新结果？

本文将会围绕上面两个核心要点，介绍动态规划算法在各类问题下的经典模型。读者应当时刻牢记上述两个核心要点，逐步构建自己的动态规划理论体系。

引入

上来就介绍各种 DP 模型似乎对新手并不友好，这里先简单过渡一下。在开始学习 DP 之前，你一定做过类似于求斐波那契数列的问题，即有一个函数定义为：

\[ \begin{cases} f_i = 1, &i = 1\\ f_i = 1, &i = 2\\ f_i = f_{i-1}+f_{i-2}, &i\ge3 \end{cases} \]

你一定可以轻松地写出下面的搜索（递归）函数：

1
2
3
4
5
6
int f(int i) {
    if (i == 1 || i == 2) {
        return 1;
    }
    return f(i - 1) + f(i - 2);
}

但是当 \(n\) 超过 \(30\) 以后，上面的程序就很难在你可忍受的时间内计算出结果了。此时就需要更高效的算法来求解这个问题。

你一定可以很轻松地看懂下面的程序：

1
2
3
4
5
6
7
8
int f(int n) {
    int f[n + 1] {};
    f[1] = f[2] = 1;
    for (int i = 3; i <= n; i++) {
        f[i] = f[i - 1] + f[i - 2];
    }
    return f[n];
}

大家习惯于将其称作 递推，因为每一个结果都是基于相邻的子结果推导而来，但这其实就是动态规划算法。在后面的内容中，你将会看到更多这种基于相邻子问题的结果推导出原问题结果的例子。

你也一定可以很轻松地看懂下面的程序：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
bool vis[10];
int ans[10];

int f(int n) {
    if (n == 1 || n == 2) {
        return 1;
    }
    if (vis[n]) {
        return ans[n];
    }
    vis[n] = true;
    return ans[n] = f(n - 1) + f(n - 2);
}

大家习惯于将其称作 记忆化搜索，因为其本质上还是搜索，只不过将中间的计算结果利用 ans 数组保存起来了而已。当然，把记忆化搜索写在这里并不代表其仅局限于此，有些时候记忆化搜索甚至可以解决高难度的题目，或者有助于你思考出递推（动态规划）写法。

线性 DP

线性 DP 顾名思义就是状态数组是线性的。注意：

  • 子串是连续的；
  • 子序列可以不是连续的。

背包 DP

区间 DP

数位 DP

树形 DP

状压 DP

概率 DP

计数 DP

  1. 动态规划杂谈 | 何逊 - (leetcode.cn) ↩