【算法训练-动态规划 零】动态规划解题框架

动态规划问题的一般形式就是求最值。动态规划其实是运筹学的一种最优化方法，只不过在计算机问题上应用比较多，比如说求最长递增子序列呀，最小编辑距离呀等等。

既然是要求最值，核心问题是什么呢？求解动态规划的核心问题是穷举。因为要求最值，肯定要把所有可行的答案穷举出来，然后在其中找最值呗。

动态规划基本概念

动态规划（Dynamic Programming，简称DP）算法是一种解决复杂问题的算法设计和优化技术，常用于解决具有重叠子问题性质和最优子结构性质的问题。它的核心思想是将一个大问题分解成一系列相互重叠的子问题，然后将子问题的解存储起来，以避免重复计算，从而节省时间。

动态规划算法通常包括以下关键步骤：

1. 定义子问题：将原问题分解成若干个子问题，并明确定义每个子问题的输入和输出。

2. 构建状态转移方程：确定每个子问题与其他子问题之间的关系，即如何通过已解决的子问题来解决当前子问题。这通常通过递归或迭代方式建立状态转移方程。

3. 初始化：初始化基本情况，通常是问题规模较小或无法再分时的边界情况。

4. 自底向上求解或使用备忘录法：根据状态转移方程，从最小的子问题开始解决，逐步构建出更大规模的问题的解。可以使用自底向上的迭代方法或备忘录法来避免重复计算。

5. 返回结果：根据状态转移方程求解出原问题的解。

动态规划广泛应用于各种领域，包括算法设计、优化问题、路径规划、序列比对、字符串处理、游戏策略等。经典的动态规划问题包括斐波那契数列、背包问题、最长公共子序列、最短路径问题。

动态规划的优点是可以显著减少重复计算，提高效率，但其缺点是需要合理定义子问题和状态转移方程，有时需要额外的内存空间来存储中间结果。因此，在解决问题时，需要仔细分析问题的性质，确定是否适合使用动态规划算法。

问题类型：一个模型三个特征

什么样的问题适合用动态规划来解决呢？换句话说，动态规划能解决的问题有什么规律可循呢？这部分理论可以总结为“一个模型三个特征”。

一个模型

首先，我们来看，什么是“一个模型”？它指的是动态规划适合解决的问题的模型。我把这个模型定义为多阶段决策最优解模型，我们一般是用动态规划来解决最优问题。

解决问题的过程，需要经历多个决策阶段。每个决策阶段都对应着一组状态。然后我们寻找一组决策序列，经过这组决策序列，能够产生最终期望求解的最优值。

三个特征

什么是“三个特征”？它们分别是最优子结构、无后效性和重复子问题

1 最优子结构

最优子结构指的是，问题的最优解包含子问题的最优解。反过来说就是，我们可以通过子问题的最优解，推导出问题的最优解。如果我们把最优子结构，对应到我们前面定义的动态规划问题模型上，那我们也可以理解为，后面阶段的状态可以通过前面阶段的状态推导出来。最优子结构，就是目前的最优解可以由以前的最优解推导出来，也就是存在状态转移公式

2 无后效性

无后效性有两层含义，第一层含义是，在推导后面阶段的状态的时候，我们只关心前面阶段的状态值，不关心这个状态是怎么一步一步推导出来的。第二层含义是，某阶段状态一旦确定，就不受之后阶段的决策影响。无后效性是一个非常“宽松”的要求。只要满足前面提到的动态规划问题模型，其实基本上都会满足无后效性。无后效性 其实就是当前状态与路径无关、当前的决定不受后面的影响，子问题的最优决策只与子问题自己相关，与原始问题无关，解决子问题时候不用考虑原始问题，就和递归只要考虑当前层状态和处理一样

3 重复子问题

不同的决策序列，到达某个相同的阶段时，可能会产生重复的状态

动态规划解题框架

虽然动态规划的核心思想就是穷举求最值，但是问题可以千变万化，穷举所有可行解其实并不是一件容易的事：

1. 需要熟练掌握递归思维，只有列出正确的「状态转移方程」，才能正确地穷举。
2. 需要判断算法问题是否具备「最优子结构」，是否能够通过子问题的最值得到原问题的最值。
3. 动态规划问题存在「重叠子问题」，如果暴力穷举的话效率会很低，所以需要使用「备忘录」或者「DP table」来优化穷举过程，避免不必要的计算

以上最难的是写出状态转移方程，给出一个思维框架

明确 base case -> 明确「状态」-> 明确「选择」 -> 定义 dp 数组/函数的含义，按上面的套路走，最后的解法代码就会是如下的框架

# 自顶向下递归的动态规划
def dp(状态1, 状态2, ...):
    for 选择 in 所有可能的选择:
        # 此时的状态已经因为做了选择而改变
        result = 求最值(result, dp(状态1, 状态2, ...))
    return result

# 自底向上迭代的动态规划
# 初始化 base case
dp[0][0][...] = base case
# 进行状态转移
for 状态1 in 状态1的所有取值：
    for 状态2 in 状态2的所有取值：
        for ...
            dp[状态1][状态2][...] = 求最值(选择1，选择2...)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

示例：暴力递归

首先看一个斐波那契数列的暴力递归方法：

int fib(int N) {
    if (N == 1 || N == 2) return 1;
    return fib(N - 1) + fib(N - 2);
}

1
2
3
4
5

这个递归树怎么理解？就是说想要计算原问题 f(20)，我就得先计算出子问题 f(19) 和 f(18)，然后要计算 f(19)，我就要先算出子问题 f(18) 和 f(17)，以此类推。最后遇到 f(1) 或者 f(2) 的时候，结果已知，就能直接返回结果，递归树不再向下生长了

递归算法的时间复杂度怎么计算？就是用子问题个数乘以解决一个子问题需要的时间

首先计算子问题个数，即递归树中节点的总数。显然二叉树节点总数为指数级别，所以子问题个数为 O(2^n)。然后计算解决一个子问题的时间，在本算法中，没有循环，只有 f(n - 1) + f(n - 2) 一个加法操作，时间为 O(1)。

所以，这个算法的时间复杂度为二者相乘，即 O(2^n)，指数级别，爆炸，观察递归树，很明显发现了算法低效的原因：存在大量重复计算，比如 f(18) 被计算了两次，而且你可以看到，以 f(18) 为根的这个递归树体量巨大，多算一遍，会耗费巨大的时间。更何况，还不止 f(18) 这一个节点被重复计算，所以这个算法及其低效。

这就是动态规划问题的第一个性质：重叠子问题

自顶向下：递归+备忘录

即然耗时的原因是重复计算，那么我们可以造一个「备忘录」，每次算出某个子问题的答案后别急着返回，先记到「备忘录」里再返回；每次遇到一个子问题先去「备忘录」里查一查，如果发现之前已经解决过这个问题了，直接把答案拿出来用，不要再耗时去计算了。

一般使用一个数组充当这个「备忘录」，当然你也可以使用哈希表（字典），思想都是一样的

int fib(int N) {
    // 备忘录全初始化为 0
    int[] memo = new int[N + 1];
    // 进行带备忘录的递归
    return dp(memo, N);
}

// 带着备忘录进行递归
int dp(int[] memo, int n) {
    // base case
    if (n == 0 || n == 1) return n;
    // 已经计算过，不用再计算了
    if (memo[n] != 0) return memo[n];
    memo[n] = dp(memo, n - 1) + dp(memo, n - 2);
    return memo[n];
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

实际上，带「备忘录」的递归算法，把一棵存在巨量冗余的递归树通过「剪枝」，改造成了一幅不存在冗余的递归图，极大减少了子问题（即递归图中节点）的个数

子问题个数，即图中节点的总数，由于本算法不存在冗余计算，子问题就是 f(1), f(2), f(3) … f(20)，数量和输入规模 n = 20 成正比，所以子问题个数为 O(n)。解决一个子问题的时间，同上，没有什么循环，时间为 O(1)，所以，本算法的时间复杂度是 O(n)，比起暴力算法，是降维打击

自底向上：状态转移表法（DP Table）

带备忘录的递归和常见的动态规划解法已经差不多了，只不过这种解法是「自顶向下」进行「递归」求解，我们更常见的动态规划代码是「自底向上」进行「递推」求解

注意我们刚才画的递归树（或者说图），是从上向下延伸，都是从一个规模较大的原问题比如说 f(20)，向下逐渐分解规模，直到 f(1) 和 f(2) 这两个 base case，然后逐层返回答案，这就叫「自顶向下」。

啥叫「自底向上」？反过来，我们直接从最底下、最简单、问题规模最小、已知结果的 f(1) 和 f(2)（base case）开始往上推，直到推到我们想要的答案 f(20)。这就是「递推」的思路，这也是动态规划一般都脱离了递归，而是由循环迭代完成计算的原因

有了上一步「备忘录」的启发，我们可以把这个「备忘录」独立出来成为一张表，通常叫做 DP table，在这张表上完成「自底向上」的推算

int fib(int N) {
    if (N == 0) return 0;
    int[] dp = new int[N + 1];
    // base case
    dp[0] = 0; dp[1] = 1;
    // 状态转移
    for (int i = 2; i <= N; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[N];
}

1
2
3
4
5
6
7
8
9
10
11
12
13

实际上，带备忘录的递归解法中的那个「备忘录」memo 数组，最终完成后就是这个解法中的 dp 数组

什么是状态转移方程？把参数 n 想做一个状态，这个状态 n 是由状态 n - 1 和状态 n - 2 转移（相加）而来，这就叫状态转移，仅此而已。 你会发现，上面的几种解法中的所有操作，例如 return f(n - 1) + f(n - 2)，dp[i] = dp[i - 1] + dp[i - 2]，以及对备忘录或 DP table 的初始化操作，都是围绕这个方程式的不同表现形式

根据斐波那契数列的状态转移方程，当前状态 n 只和之前的 n-1, n-2 两个状态有关，其实并不需要那么长的一个 DP table 来存储所有的状态，只要想办法存储之前的两个状态就行了

int fib(int n) {
    if (n == 0 || n == 1) {
        // base case
        return n;
    }
    // 分别代表 dp[i - 1] 和 dp[i - 2]
    int dp_i_1 = 1, dp_i_2 = 0;
    for (int i = 2; i <= n; i++) {
        // dp[i] = dp[i - 1] + dp[i - 2];
        int dp_i = dp_i_1 + dp_i_2;
        // 滚动更新
        dp_i_2 = dp_i_1;
        dp_i_1 = dp_i;
    }
    return dp_i_1;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

所以，可以进一步优化，把空间复杂度降为 O(1)

动态规划解题基本步骤及应用领域

动态规划（Dynamic Programming，简称DP）是一种解决复杂问题的算法设计技术，常用于优化问题和组合问题的求解。它通过将原问题分解成子问题，并保存子问题的解，以避免重复计算，从而提高算法的效率。动态规划通常用于解决具有重叠子问题和最优子结构性质的问题。

动态规划的基本思想可以总结为以下几个步骤：

1. 定义问题的状态：首先要明确定义问题的状态，这些状态可以用来描述问题的各种情况。

2. 找到状态转移方程：状态转移方程描述了问题之间的联系，即如何从一个状态转移到另一个状态。这通常涉及到问题的递归关系，通过这个关系可以从较小规模的子问题得到更大规模的问题的解。

3. 初始化状态：确定初始状态的值，这通常是问题规模最小的情况下的解。

4. 自底向上或自顶向下求解：动态规划可以采用自底向上（Bottom-Up）或自顶向下（Top-Down）的方式求解问题。自底向上是从最小的状态开始逐步计算，直到得到最终问题的解；自顶向下是从最终问题开始，递归地计算子问题的解，直到达到最小状态。

5. 根据问题的要求，从状态中找到最终解。

动态规划常见的应用领域包括：

1. 最长公共子序列问题：在两个序列中找到一个最长的共同子序列，用于比较字符串相似性。

2. 背包问题：在给定一定容量的背包和一组物品的情况下，选择一些物品放入背包，使得物品的总价值最大或总重量不超过背包容量。

3. 最短路径问题：求解图中两点之间的最短路径，如Dijkstra算法和Floyd-Warshall算法。

4. 硬币找零问题：给定一组硬币面额和一个目标金额，找到使用最少数量的硬币组合成目标金额。

5. 斐波那契数列问题：求解斐波那契数列的第n个数，通过动态规划可以避免重复计算。

动态规划是一种强大的问题求解方法，但它并不适用于所有类型的问题。在使用动态规划时，需要仔细分析问题的性质，确保问题具有重叠子问题和最优子结构性质，以确保动态规划算法能够有效地解决问题。

贪心算法、动态规划、回溯算法

这三个算法解决问题的模型，都可以抽象成多阶段决策最优解模型，

• 回溯算法是个“万金油”。基本上能用的动态规划、贪心解决的问题，我们都可以用回溯算法解决。回溯算法相当于穷举搜索。穷举所有的情况，然后对比得到最优解。不过，回溯算法的时间复杂度非常高，是指数级别的，只能用来解决小规模数据的问题。对于大规模数据的问题，用回溯算法解决的执行效率就很低了。解决最多的问题，性能最差
• 尽管动态规划比回溯算法高效，但是，并不是所有问题，都可以用动态规划来解决。能用动态规划解决的问题，需要满足三个特征，最优子结构、无后效性和重复子问题。在重复子问题这一点上，动态规划和分治算法的区分非常明显。分治算法要求分割成的子问题，不能有重复子问题，而动态规划正好相反，动态规划之所以高效，就是因为回溯算法实现中存在大量的重复子问题。解决较多的问题，性能较好
• 贪心算法实际上是动态规划算法的一种特殊情况。它解决问题起来更加高效，代码实现也更加简洁。不过，它可以解决的问题也更加有限。它能解决的问题需要满足三个条件，最优子结构、无后效性和贪心选择性（这里我们不怎么强调重复子问题）。其中，最优子结构、无后效性跟动态规划中的无异。“贪心选择性”的意思是，通过局部最优的选择，能产生全局的最优选择。每一个阶段，我们都选择当前看起来最优的决策，所有阶段的决策完成之后，最终由这些局部最优解构成全局最优解，解决最少的问题，性能最好

动态规划、递归、分治的区别

下面是动态规划、递归和分治这三种算法的相同点和不同点的表格展示：

这个表格概括了动态规划、递归和分治算法之间的一些主要相同点和不同点。需要注意的是，这些算法的选择取决于具体问题的性质和要求，有时候也可以根据问题的特点将它们结合使用，以获得更好的性能和效果。

动态规划、递归、分治处理的题目分类

适用于这些算法思想的题目

动态规划处理的高频算法题

动态规划是一个非常强大的算法技巧，适用于解决各种高频的算法问题。以下是一些使用动态规划解决的常见高频算法题目：

1. 斐波那契数列问题：计算斐波那契数列的第n个数，可以使用动态规划来避免指数级的重复计算。

2. 背包问题：如 0-1 背包问题、完全背包问题、多重背包问题等，动态规划可用于优化资源分配问题。

3. 最长公共子序列问题：寻找两个字符串的最长公共子序列，动态规划可用于解决字符串匹配和相似性比较问题。

4. 最长递增子序列问题：寻找一个数组中最长的递增子序列，常用于优化问题和排序问题。

5. 最短路径问题：如 Dijkstra 算法、Floyd-Warshall 算法，用于在图中找到最短路径或最短距离。

6. 编辑距离问题：计算两个字符串之间的最小编辑操作数，如插入、删除和替换操作。

7. 股票买卖问题：寻找股票价格数组中的最佳买卖时机，以获得最大的利润。

8. 子集和问题：确定给定集合中是否存在一个子集，其元素之和等于特定目标值。

9. 矩阵链乘法问题：在给定一组矩阵的情况下，确定它们相乘的最佳顺序以最小化乘法运算的次数。

10. 字符串匹配问题：如正则表达式匹配、通配符匹配等，用于模式匹配和文本搜索。

这些问题只是动态规划可以解决的众多示例之一。动态规划的思想可以应用于各种优化和最优化问题，它的关键是将问题分解成子问题并找到适当的状态转移规则。因此，当你面对一个复杂的问题时，考虑是否可以使用动态规划来提高问题求解的效率和准确性。

分治算法处理的高频算法题

分治算法是一种重要的算法技巧，适用于解决各种高频的算法问题，特别是分而治之的思想。以下是一些使用分治算法解决的常见高频算法题目：

1. 归并排序：分治算法的经典示例之一，用于将一个大数组分割成较小的子数组，排序子数组，然后将它们合并以得到有序数组。

2. 快速排序：另一种基于分治思想的排序算法，通过选择一个基准元素，将数组划分成两个子数组，然后递归地对子数组进行排序。

3. 连续子数组的最大和：给定一个整数数组，查找具有最大和的连续子数组。分治算法可以用于高效解决这个问题。

4. 求解最近点对问题：给定一个包含多个点的平面，找到最接近的一对点。该问题可以通过分治算法以较低的时间复杂度解决。

5. 矩阵乘法：分治算法可以用于将矩阵分割成子矩阵，然后递归地进行矩阵乘法操作，以减少计算次数。

6. 大整数乘法：用于计算两个大整数的乘积，分治算法可以用于将大整数分解为较小的整数，并递归地计算它们的乘积。

7. 众数问题：查找数组中出现次数超过一半的元素，分治算法可以在线性时间内解决这个问题。

8. 合并K个有序链表：将K个有序链表合并为一个有序链表，分治算法可以用于高效解决这个问题。

9. 寻找第K大/小的元素：在一个未排序的数组中找到第K大或第K小的元素，分治算法可以用于解决这个问题。

10. 求解凸多边形的最小包围矩形：给定一个凸多边形，找到包围它的最小矩形。分治算法可用于高效计算最小包围矩形。

这些问题只是分治算法可以解决的众多示例之一。分治算法的关键思想是将问题分解为相互独立的子问题，然后将子问题的解合并以得到原问题的解。当你面对一个需要分而治之的问题时，考虑是否可以使用分治算法来提高问题求解的效率和准确性。

递归算法处理的高频算法题

递归算法是一种常见且强大的算法技巧，适用于解决各种高频的算法问题。以下是一些使用递归算法解决的常见高频算法题目：

1. 二叉树遍历：包括前序遍历、中序遍历、后序遍历等，用于访问和处理二叉树的节点。

2. 分解问题：许多问题可以通过将它们分解为更小的相似子问题来解决，例如斐波那契数列、汉诺塔问题等。

3. 递归的数据结构：如链表、树、图等数据结构的处理通常使用递归来实现。

4. 组合和排列问题：生成所有可能的组合或排列，如子集生成、排列生成等。

5. 回溯算法：解决一些组合优化问题，如八皇后问题、数独问题等。

6. 图的遍历：深度优先搜索（DFS）和广度优先搜索（BFS）是递归的常见应用，用于解决图相关的问题。

7. 递归的搜索和查找：二分查找、树的搜索、图的最短路径等问题可以使用递归算法解决。

8. 分治算法：分治算法的核心思想就是递归，如归并排序、快速排序等。

9. 递归背包问题：解决背包问题的变种，如动态规划中的背包问题。

10. 字符串处理：字符串匹配、编辑距离、正则表达式匹配等问题通常可以使用递归来解决。

这些问题只是递归算法可以解决的众多示例之一。递归算法的关键思想是将问题分解为更小的相似问题，并通过递归调用自身来解决这些子问题。当你面对一个需要不断分解问题的情况时，考虑是否可以使用递归来解决，但需要小心避免无限递归，确保有适当的终止条件。