01.Dynamic-Programming-Basic.md

1. 动态规划简介

1.1 动态规划的定义

动态规划（Dynamic Programming）：简称 DP，是一种求解多阶段决策过程最优化问题的方法。在动态规划中，通过把原问题分解为相对简单的子问题，先求解子问题，再由子问题的解而得到原问题的解。

动态规划最早由理查德 · 贝尔曼于 1957 年在其著作「动态规划（Dynamic Programming）」一书中提出。这里的 Programming 并不是编程的意思，而是指一种「表格处理方法」，即将每一步计算的结果存储在表格中，供随后的计算查询使用。

1.2 动态规划的核心思想

动态规划的核心思想：

1. 把「原问题」分解为「若干个重叠的子问题」，每个子问题的求解过程都构成一个 「阶段」。在完成一个阶段的计算之后，动态规划方法才会执行下一个阶段的计算。
2. 在求解子问题的过程中，按照「自顶向下的记忆化搜索方法」或者「自底向上的递推方法」求解出「子问题的解」，把结果存储在表格中，当需要再次求解此子问题时，直接从表格中查询该子问题的解，从而避免了大量的重复计算。

这看起来很像是分治算法，但动态规划与分治算法的不同点在于：

1. 适用于动态规划求解的问题，在分解之后得到的子问题往往是相互联系的，会出现若干个重叠子问题。
2. 使用动态规划方法会将这些重叠子问题的解保存到表格里，供随后的计算查询使用，从而避免大量的重复计算。

1.3 动态规划的简单例子

下面我们先来通过一个简单的例子来介绍一下什么是动态规划算法，然后再来讲解动态规划中的各种术语。

斐波那契数列：数列由 $f(0) = 1, f(1) = 2$ 开始，后面的每一项数字都是前面两项数字的和。也就是：

$f(n) = \begin{cases} 0 & n = 0 \cr 1 & n = 1 \cr f(n - 2) + f(n - 1) & n > 1 \end{cases}$

通过公式 $f(n) = f(n - 2) + f(n - 1)$，我们可以将原问题 $f(n)$ 递归地划分为 $f(n - 2)$ 和 $f(n - 1)$ 这两个子问题。其对应的递归过程如下图所示：

从图中可以看出：如果使用传统递归算法计算 $f(5)$，需要先计算 $f(3)$ 和 $f(4)$，而在计算 $f(4)$ 时还需要计算 $f(3)$，这样 $f(3)$ 就进行了多次计算。同理 $f(0)$、$f(1)$、$f(2)$ 都进行了多次计算，从而导致了重复计算问题。

为了避免重复计算，我们可以使用动态规划中的「表格处理方法」来处理。

这里我们使用「自底向上的递推方法」求解出子问题 $f(n - 2)$ 和 $f(n - 1)$ 的解，然后把结果存储在表格中，供随后的计算查询使用。具体过程如下：

1. 定义一个数组 $dp$，用于记录斐波那契数列中的值。
2. 初始化 $dp[0] = 0, dp[1] = 1$。
3. 根据斐波那契数列的递推公式 $f(n) = f(n - 1) + f(n - 2)$，从 $dp(2)$ 开始递推计算斐波那契数列的每个数，直到计算出 $dp(n)$。
4. 最后返回 $dp(n)$ 即可得到第 $n$ 项斐波那契数。

具体代码如下：

class Solution:
    def fib(self, n: int) -> int:
        if n == 0:
            return 0
        if n == 1:
            return 1

        dp = [0 for _ in range(n + 1)]
        dp[0] = 0
        dp[1] = 1

        for i in range(2, n + 1):
            dp[i] = dp[i - 2] + dp[i - 1]

        return dp[n]

这种使用缓存（哈希表、集合或数组）保存计算结果，从而避免子问题重复计算的方法，就是「动态规划算法」。

2. 动态规划的特征

究竟什么样的问题才可以使用动态规划算法解决呢？

首先，能够使用动态规划方法解决的问题必须满足以下三个特征：

1. 最优子结构性质
2. 重叠子问题性质
3. 无后效性

2.1 最优子结构性质

最优子结构：指的是一个问题的最优解包含其子问题的最优解。

举个例子，如下图所示，原问题 $S = \lbrace a_1, a_2, a_3, a_4 \rbrace$，在 $a_1$ 步我们选出一个当前最优解之后，问题就转换为求解子问题 $S_{\text{子问题}} = \lbrace a_2, a_3, a_4 \rbrace$。如果原问题 $S$ 的最优解可以由「第 $a_1$ 步得到的局部最优解」和「 $S_{\text{子问题}}$ 的最优解」构成，则说明该问题满足最优子结构性质。

也就是说，如果原问题的最优解包含子问题的最优解，则说明该问题满足最优子结构性质。

2.2 重叠子问题性质

重叠子问题性质：指的是在求解子问题的过程中，有大量的子问题是重复的，一个子问题在下一阶段的决策中可能会被多次用到。如果有大量重复的子问题，那么只需要对其求解一次，然后用表格将结果存储下来，以后使用时可以直接查询，不需要再次求解。

之前我们提到的「斐波那契数列」例子中，$f(0)$、$f(1)$、$f(2)$、$f(3)$ 都进行了多次重复计算。动态规划算法利用了子问题重叠的性质，在第一次计算 $f(0)$、$f(1)$、$f(2)$、$f(3)$ 时就将其结果存入表格，当再次使用时可以直接查询，无需再次求解，从而提升效率。

2.3 无后效性

无后效性：指的是子问题的解（状态值）只与之前阶段有关，而与后面阶段无关。当前阶段的若干状态值一旦确定，就不再改变，不会再受到后续阶段决策的影响。

也就是说，一旦某一个子问题的求解结果确定以后，就不会再被修改。

举个例子，下图是一个有向无环带权图，我们在求解从 $A$ 点到 $F$ 点的最短路径问题时，假设当前已知从 $A$ 点到 $D$ 点的最短路径（$2 + 7 = 9$）。那么无论之后的路径如何选择，都不会影响之前从 $A$ 点到 $D$ 点的最短路径长度。这就是「无后效性」。

而如果一个问题具有「后效性」，则可能需要先将其转化或者逆向求解来消除后效性，然后才可以使用动态规划算法。

3. 动态规划的基本思路

如下图所示，我们在使用动态规划方法解决某些最优化问题时，可以将解决问题的过程按照一定顺序（时间顺序、空间顺序或其他顺序）分解为若干个相互联系的「阶段」。然后按照顺序对每一个阶段做出「决策」，这个决策既决定了本阶段的效益，也决定了下一阶段的初始状态。依次做完每个阶段的决策之后，就得到了一个整个问题的决策序列。

这样就将一个原问题分解为了一系列的子问题，再通过逐步求解从而获得最终结果。

这种前后关联、具有链状结构的多阶段进行决策的问题也叫做「多阶段决策问题」。

通常我们使用动态规划方法来解决问题的基本思路如下：

1. 划分阶段：将原问题按顺序（时间顺序、空间顺序或其他顺序）分解为若干个相互联系的「阶段」。划分后的阶段⼀定是有序或可排序的，否则问题⽆法求解。
   • 这里的「阶段」指的是⼦问题的求解过程。每个⼦问题的求解过程都构成⼀个「阶段」，在完成前⼀阶段的求解后才会进⾏后⼀阶段的求解。
2. 定义状态：将和子问题相关的某些变量（位置、数量、体积、空间等等）作为一个「状态」表示出来。状态的选择要满⾜⽆后效性。
   • 一个「状态」对应一个或多个子问题，所谓某个「状态」下的值，指的就是这个「状态」所对应的子问题的解。
3. 状态转移：根据「上一阶段的状态」和「该状态下所能做出的决策」，推导出「下一阶段的状态」。或者说根据相邻两个阶段各个状态之间的关系，确定决策，然后推导出状态间的相互转移方式（即「状态转移方程」）。
4. 初始条件和边界条件：根据问题描述、状态定义和状态转移方程，确定初始条件和边界条件。
5. 最终结果：确定问题的求解目标，然后按照一定顺序求解每一个阶段的问题。最后根据状态转移方程的递推结果，确定最终结果。

4. 动态规划的应用

动态规划相关的问题往往灵活多变，思维难度大，没有特别明显的套路，并且经常会在各类算法竞赛和面试中出现。

动态规划问题的关键点在于「如何状态设计」和「推导状态转移条件」，还有各种各样的「优化方法」。这类问题一定要多练习、多总结，只有接触的题型多了，才能熟练掌握动态规划思想。

下面来介绍几道关于动态规划的基础题目。

4.1 斐波那契数

4.1.1 题目链接

• 509. 斐波那契数 - 力扣

4.1.2 题目大意

描述：给定一个整数 $n$。

要求：计算第 $n$ 个斐波那契数。

说明：

• 斐波那契数列的定义如下：
  • $f(0) = 0, f(1) = 1$。
  • $f(n) = f(n - 1) + f(n - 2)$，其中 $n > 1$。
• $0 \le n \le 30$。

示例：

• 示例 1：

输入：n = 2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1

• 示例 2：

输入：n = 3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2

4.1.3 解题思路

1. 划分阶段

我们可以按照整数顺序进行阶段划分，将其划分为整数 $0 \sim n$。

2. 定义状态

定义状态 $dp[i]$ 为：第 $i$ 个斐波那契数。

3. 状态转移方程

根据题目中所给的斐波那契数列的定义 $f(n) = f(n - 1) + f(n - 2)$，则直接得出状态转移方程为 $dp[i] = dp[i - 1] + dp[i - 2]$。

4. 初始条件

根据题目中所给的初始条件 $f(0) = 0, f(1) = 1$ 确定动态规划的初始条件，即 $dp[0] = 0, dp[1] = 1$。

5. 最终结果

根据状态定义，最终结果为 $dp[n]$，即第 $n$ 个斐波那契数为 $dp[n]$。

4.1.4 代码

class Solution:
    def fib(self, n: int) -> int:
        if n <= 1:
            return n

        dp = [0 for _ in range(n + 1)]
        dp[0] = 0
        dp[1] = 1
        for i in range(2, n + 1):
            dp[i] = dp[i - 2] + dp[i - 1]

        return dp[n]

4.1.5 复杂度分析

• 时间复杂度：$O(n)$。一重循环遍历的时间复杂度为 $O(n)$。
• 空间复杂度：$O(n)$。用到了一维数组保存状态，所以总体空间复杂度为 $O(n)$。

4.2 爬楼梯

4.2.1 题目链接

• 70. 爬楼梯 - 力扣

4.2.2 题目大意

描述：假设你正在爬楼梯。需要 $n$ 阶你才能到达楼顶。每次你可以爬 $1$ 或 $2$ 个台阶。现在给定一个整数 $n$。

要求：计算出有多少种不同的方法可以爬到楼顶。

说明：

• $1 \le n \le 45$。

示例：

• 示例 1：

输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶

• 示例 2：

输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

4.2.3 解题思路

1. 划分阶段

我们按照台阶的阶层划分阶段，将其划分为 $0 \sim n$ 阶。

2. 定义状态

定义状态 $dp[i]$ 为：爬到第 $i$ 阶台阶的方案数。

3. 状态转移方程

根据题目大意，每次只能爬 $1$ 或 $2$ 个台阶。则第 $i$ 阶楼梯只能从第 $i - 1$ 阶向上爬 $1$ 阶上来，或者从第 $i - 2$ 阶向上爬 $2$ 阶上来。所以可以推出状态转移方程为 $dp[i] = dp[i - 1] + dp[i - 2]$。

4. 初始条件

• 第 $0$ 层台阶方案数：可以看做 $1$ 种方法（从 $0$ 阶向上爬 $0$ 阶），即 $dp[1] = 1$。
• 第 $1$ 层台阶方案数：$1$ 种方法（从 $0$ 阶向上爬 $1$ 阶），即 $dp[1] = 1$。
• 第 $2$ 层台阶方案数：$2$ 中方法（从 $0$ 阶向上爬 $2$ 阶，或者从 $1$ 阶向上爬 $1$ 阶）。

5. 最终结果

根据状态定义，最终结果为 $dp[n]$，即爬到第 $n$ 阶台阶（即楼顶）的方案数为 $dp[n]$。

虽然这道题跟上一道题的状态转移方程都是 $dp[i] = dp[i - 1] + dp[i - 2]$，但是两道题的考察方式并不相同，一定程度上也可以看出来动态规划相关题目的灵活多变。

4.2.4 代码

class Solution:
    def climbStairs(self, n: int) -> int:
        dp = [0 for _ in range(n + 1)]
        dp[0] = 1
        dp[1] = 1
        for i in range(2, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2]
        
        return dp[n]

4.2.5 复杂度分析

• 时间复杂度：$O(n)$。一重循环遍历的时间复杂度为 $O(n)$。
• 空间复杂度：$O(n)$。用到了一维数组保存状态，所以总体空间复杂度为 $O(n)$。因为 $dp[i]$ 的状态只依赖于 $dp[i - 1]$ 和 $dp[i - 2]$，所以可以使用 $3$ 个变量来分别表示 $dp[i]$、$dp[i - 1]$、$dp[i - 2]$，从而将空间复杂度优化到 $O(1)$。

4.3 不同路径

4.3.1 题目链接

• 62. 不同路径 - 力扣

4.3.2 题目大意

描述：给定两个整数 $m$ 和 $n$，代表大小为 $m \times n$ 的棋盘， 一个机器人位于棋盘左上角的位置，机器人每次只能向右、或者向下移动一步。

要求：计算出机器人从棋盘左上角到达棋盘右下角一共有多少条不同的路径。

说明：

• $1 \le m, n \le 100$。
• 题目数据保证答案小于等于 $2 \times 10^9$。

示例：

• 示例 1：

输入：m = 3, n = 7
输出：28

• 示例 2：

输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下

4.3.3 解题思路

1. 划分阶段

按照路径的结尾位置（行位置、列位置组成的二维坐标）进行阶段划分。

2. 定义状态

定义状态 $dp[i][j]$ 为：从左上角到达 $(i, j)$ 位置的路径数量。

3. 状态转移方程

因为我们每次只能向右、或者向下移动一步，因此想要走到 $(i, j)$，只能从 $(i - 1, j)$ 向下走一步走过来；或者从 $(i, j - 1)$ 向右走一步走过来。所以可以写出状态转移方程为：$dp[i][j] = dp[i - 1][j] + dp[i][j - 1]$，此时 $i > 0, j > 0$。

4. 初始条件

• 从左上角走到 $(0, 0)$ 只有一种方法，即 $dp[0][0] = 1$。
• 第一行元素只有一条路径（即只能通过前一个元素向右走得到），所以 $dp[0][j] = 1$。
• 同理，第一列元素只有一条路径（即只能通过前一个元素向下走得到），所以 $dp[i][0] = 1$。

5. 最终结果

根据状态定义，最终结果为 $dp[m - 1][n - 1]$，即从左上角到达右下角 $(m - 1, n - 1)$ 位置的路径数量为 $dp[m - 1][n - 1]$。

4.3.4 代码

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[0 for _ in range(n)] for _ in range(m)]
        
        for j in range(n):
            dp[0][j] = 1
        for i in range(m):
            dp[i][0] = 1

        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
        
        return dp[m - 1][n - 1]

4.3.5 复杂度分析

• 时间复杂度：$O(m \times n)$。初始条件赋值的时间复杂度为 $O(m + n)$，两重循环遍历的时间复杂度为 $O(m \times n)$，所以总体时间复杂度为 $O(m \times n)$。
• 空间复杂度：$O(m \times n)$。用到了二维数组保存状态，所以总体空间复杂度为 $O(m \times n)$。因为 $dp[i][j]$ 的状态只依赖于上方值 $dp[i - 1][j]$ 和左侧值 $dp[i][j - 1]$，而我们在进行遍历时的顺序刚好是从上至下、从左到右。所以我们可以使用长度为 $n$ 的一维数组来保存状态，从而将空间复杂度优化到 $O(n)$。

参考资料

• 【文章】动态规划基础 - OI Wiki
• 【文章】动态规划 1 ——基本概念 - 知乎
• 【文章】动态规划算法 | 曹世宏的博客
• 【文章】动态规划之初识动规：有了四步解题法模板，再也不害怕动态规划！ - 知乎
• 【文章】第 6 节 最优子结构、重复子问题、无后效性 | 算法吧
• 【书籍】算法训练营 陈小玉 著
• 【书籍】趣学算法 陈小玉 著
• 【书籍】算法竞赛进阶指南 - 李煜东 著
• 【书籍】ACM-ICPC 程序设计系列 - 算法设计与实现 - 陈宇 吴昊 主编