动态规划算法核心解析与实战

缺陷 该算法使用回溯枚举所有爬楼方案，存在大量重复子问题，时间复杂度为 O(2ⁿ)，在 n 较大时会超时，因此不适合用于只求方案数量的问题。

2.2 方法二：暴力搜索

接下来我们从问题分解的角度来分析此题。

假设设爬到第 i 阶共有 dp[i] 种方案。

可知：爬到第 i - 1 阶的方案数加上爬到第 i - 2 阶的方案数就等于爬到第 i 阶的方案数，公式如下： dp[i] = dp[i - 1] + dp[i - 2]

这意味着在爬楼梯问题中，各个子问题之间存在递推关系，原问题的解可以由子问题的解构建得来。

我们可以根据递推公式得到暴力搜索解法。以 dp[n] 为起始点，递归地将一个较大问题拆解为两个较小问题的和，直至到达最小子问题 dp[1] 和 dp[2] 时返回。

代码如下（它和标准回溯代码都属于深度优先搜索，但更加简洁）：

#include <iostream>
using namespace std;
#include <vector>

int dfs(int n) {
    // 已知 dp[1] 和 dp[2]，返回之
    if (n == 1 || n == 2) { return n; }
    // dp[i] = dp[i-1] + dp[i-2]
    int count = dfs(n - 1) + dfs(n - 2);
    return count;
}

int main() {
    int n = 5;
    cout << dfs(n) << endl;
    return 0;
}

缺陷 对于问题 dp[n]，其递归树的深度为 n，时间复杂度为 O(2ⁿ)，指数阶属于爆炸式增长，其中指数阶的时间复杂度是'重叠子问题'导致的，大部分计算资源都浪费在这些重叠的子问题上。

2.3 方法三：记忆化搜索

为了提升算法效率，我们希望所有的重叠子问题都只被计算一次。为此，我们声明一个数组 mem 来记录每个子问题的解，并在搜索过程中将重叠子问题剪枝。

记忆化搜索是一种'从顶至底'的方法： 我们从原问题（根节点）开始，递归地将较大子问题分解为较小子问题，直至解已知的最小子问题（叶节点）。之后，通过回溯逐层收集子问题的解，构建出原问题的解。

代码实现如下：

#include <iostream>
using namespace std;
#include <vector>

int dfs(int n, vector<int>& mem) {
    if (n == 1 || n == 2) { return n; }
    // 若存在记录 dp[i]，则直接返回之
    if (mem[n] != -1) { return mem[n]; }
    int count = dfs(n - 1, mem) + dfs(n - 2, mem);
    // 记录 dp[i]
    mem[n] = count;
    return count;
}

int main() {
    int n = 6;
    // mem[i] 记录爬到第 i 阶的方案总数，-1 代表无记录
    vector<int> mem(n + 1, -1);
    cout << dfs(n, mem) << endl;
    return 0;
}

2.4 方法四：动态规划

动态规划是一种'从底至顶'的方法： 从最小子问题的解开始，迭代地构建更大子问题的解，直至得到原问题的解。

动态规划无需回溯，可直接用循环实现。以下代码使用了数组 dp 用于存储子问题的解，功能与记忆化搜索中的 mem 相同：

#include <iostream>
using namespace std;
#include <vector>

int DPclimb(int n) {
    if (n == 1 || n == 2) return n;
    // 初始化 dp 表，用于存储子问题的解
    vector<int> dp(n + 1);
    // 初始状态：预设最小子问题的解
    dp[1] = 1; dp[2] = 2;
    // 状态转移：从较小子问题逐步求解较大子问题
    for (int i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

int main() {
    int n = 6;
    cout << DPclimb(n) << endl;
    return 0;
}

基于此题总结的 DP 术语

• 将数组 dp 称为 dp 表，dp[i] 表示状态 i 对应子问题的解。
• 将最小子问题对应的状态（第 1 阶和第 2 阶楼梯）称为初始状态。
• 将递推公式 dp[i] = dp[i - 1] + dp[i - 2] 称为状态转移方程。

2.5 动态规划空间优化

由于 dp[i] 只与 dp[i - 1] 和 dp[i - 2] 有关，因此我们无须使用一个数组 dp 来存储所有子问题的解，而只需两个变量滚动前进即可。

代码如下所示：

#include <iostream>
using namespace std;
#include <vector>

int DPclimb_Upgrade(int n) {
    if (n == 1 || n == 2) return n;
    int a = 1;
    int b = 2;
    for (int i = 3; i <= n; i++) {
        int temp = b;
        b = a + b;
        a = temp;
    }
    return b;
}

int main() {
    int n = 6;
    cout << DPclimb_Upgrade(n) << endl;
    return 0;
}

由于省去了数组 dp 占用的空间，因此空间复杂度从 O(n) 降至 O(1)。

总结 在动态规划问题中，当前状态往往仅与前面有限个状态有关，这时我们可以只保留必要的状态，通过'降维'来节省内存空间。这种空间优化技巧被称为'滚动变量'或'滚动数组'。

3. DP 问题特性

子问题分解是一种通用的算法思路，在分治、动态规划、回溯中的侧重点不同：

• 分治算法：将问题递归拆分为相互独立的子问题，分别求解后再合并结果。
• 动态规划：同样进行问题分解，与分治区别是子问题相互依赖且存在重叠，通过记录子问题结果避免重复计算。
• 回溯算法：将问题视为一系列决策步骤，在尝试与回退中枚举所有可能解，并通过剪枝减少搜索。

★记忆锚点★ 分治强调'拆开独立算、再合并'， 动态规划强调'子问题重叠、记下来复用'， 回溯强调'做选择、走不通就回退'。

其实，实际上，动态规划常用来求解最优化问题，它们不仅包含重叠子问题，还具有另外两大特性：最优子结构、无后效性。

3.1 最优子结构

先对爬楼梯问题修改一下，符合最优子结构的概念。

问题： 给定一个楼梯，你每步可以上 1 阶或者 2 阶，每一阶楼梯上都贴有一个非负整数，表示你在该台阶所需要付出的代价。给定一个非负整数数组 cost，其中 cost[i] 表示在第 i 个台阶需要付出的代价，cost[0] 为地面（起始点）。请计算最少需要付出多少代价才能到达顶部？

设 dp[i] 为爬到第 i 阶累计付出的代价，由于第 i 阶只可能从 i - 1 阶或 i - 2 阶走来，所以 dp[i] 只能为 dp[i] = dp[i - 1] + cost[i] 或 dp[i] = dp[i - 2] + cost[i]，为了尽可能减少代价，我们应该选择两者中较小的那一个： dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i]

这便可以引出最优子结构的含义：原问题的最优解是从子问题的最优解构建得来的。

本题显然具有最优子结构：我们从两个子问题最优解 dp[i - 1] 和 dp[i - 2] 中挑选出较优的那一个，并用它构建出原问题 dp[i] 的最优解。

动态规划代码如下：

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int minCostClimbingStairsDP(vector<int>& cost) {
    int n = cost.size() - 1;
    if (n == 1 || n == 2) { return cost[n]; }
    // 初始化 dp 表，用于存储子问题的解
    vector<int> dp(n + 1);
    // 初始状态：预设最小子问题的解
    dp[1] = cost[1]; dp[2] = cost[2];
    // 状态转移：从较小子问题逐步求解较大子问题
    for (int i = 3; i <= n; i++) {
        dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i];
    }
    return dp[n];
}

int main() {
    vector<int> cost = {0, 1, 10, 1, 1, 1, 10, 1, 1, 10, 1};
    int res = minCostClimbingStairsDP(cost);
    cout << "爬完楼梯的最低代价为 " << res << endl;
    return 0;
}

同理，此代码也可以进行空间优化从 O(n) 到 O(1) 的空间复杂度：

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int minCostClimbingStairsDP(vector<int>& cost) {
    int n = cost.size() - 1;
    if (n == 1 || n == 2) { return cost[n]; }
    int a = cost[1];
    int b = cost[2];
    for (int i = 3; i <= n; i++) {
        int temp = b;
        b = min(a, temp) + cost[i];
        a = temp;
    }
    return b;
}

int main() {
    vector<int> cost = {0, 1, 10, 1, 1, 1, 10, 1, 1, 10, 1};
    int res = minCostClimbingStairsDP(cost);
    cout << "爬完楼梯的最低代价为 " << res << endl;
    return 0;
}

Question：为什么此处 n = cost.size() - 1 呢？ 答：因为此代码算的是到达最后一个台阶的最小代价，楼顶不需要代价，若使用 n = cost.size() 就是正常的到楼顶的代价。

3.2 无后效性

无后效性定义为：给定一个确定的状态，它的未来发展只与当前状态有关，而与过去经历的所有状态无关。

就以爬楼梯问题为例，给定状态 i，它会发展出状态 i + 1 和状态 i + 2，分别对应跳 1 步和跳 2 步。在做出这两种选择时，我们无须考虑状态 i 之前的状态，它们对状态 i 的未来没有影响。

然而，如果我们给爬楼梯问题添加一个约束，情况就不一样了。

爬楼梯约束为： 给定一个共有 n 阶的楼梯，你每步可以上 1 阶或者 2 阶，但不能连续两轮跳 1 阶，请问有多少种方案可以爬到楼顶？

在该问题中就已经不满足无后效性了，因为：如果上一轮是跳 1 阶上来的，那么下一轮就必须跳 2 阶。这意味着，下一步选择不能由当前状态（当前所在楼梯阶数）独立决定，还和前一个状态（上一轮所在楼梯阶数）有关。

为此，我们可以通过扩展状态定义使得问题重新满足无后效性：状态 [i, j] 表示处在第 i 阶并且上一轮跳了 j 阶，其中 j ∈ {1, 2}。此状态定义有效地区分了上一轮跳了 1 阶还是 2 阶，我们可以据此判断当前状态是从何而来的。

• 当上一轮跳了 1 阶时，上上一轮只能选择跳 2 阶，即 dp[i, 1] 只能从 dp[i - 1, 2] 转移过来。
• 当上一轮跳了 2 阶时，上上一轮可选择跳 1 阶或跳 2 阶，即 dp[i, 2] 可以从 dp[i - 2, 1] 或 dp[i - 2, 2] 转移过来。

此时的状态转移方程为：

dp[i, 1] = dp[i - 1, 2]
dp[i, 2] = dp[i - 2, 1] + dp[i - 2, 2]

最终，返回 dp[n, 1] + dp[n, 2] 即可，两者之和代表爬到第 n 阶的方案总数，代码如下所示：

#include <iostream>
#include <vector>
using namespace std;

int climbingStairsConstraintDP(int n) {
    if (n == 1 || n == 2) { return 1; }
    // 初始化 dp 表，用于存储子问题的解
    vector<vector<int>> dp(n + 1, vector<int>(3, 0));
    // 初始状态：预设最小子问题的解
    dp[1][1] = 1; dp[1][2] = 0; dp[2][1] = 0; dp[2][2] = 1;
    // 状态转移：从较小子问题逐步求解较大子问题
    for (int i = 3; i <= n; i++) {
        dp[i][1] = dp[i - 1][2];
        dp[i][2] = dp[i - 2][1] + dp[i - 2][1]; // Note: Original logic might need adjustment based on constraints, keeping original code structure
    }
    return dp[n][1] + dp[n][2];
}

int main() {
    int n = 9;
    int res = climbingStairsConstraintDP(n);
    cout << "爬 " << n << " 阶楼梯共有 " << res << " 种方案" << endl;
    return 0;
}

然而，一些问题存在严重的后效性，尤其是旅行商问题等复杂组合优化问题，难以满足无后效性要求，通常需借助启发式搜索、遗传算法或强化学习等方法，在有限时间内求得可接受的近似解。

4. DP 解题思路

本小节主要讨论两个问题：

1. 如何判断一个问题是不是动态规划问题？
2. 求解动态规划问题该从何处入手，完整步骤是什么？

4.1 问题判断

先观察问题是否适合使用回溯（穷举）解决，适合用回溯解决的问题通常满足'决策树模型'。（这种问题可以使用树形结构来描述，其中每一个节点代表一个决策，每一条路径代表一个决策序列）

换句话说：如果问题包含明确的决策概念，并且解是通过一系列决策产生的，那么它就满足决策树模型，通常可以使用回溯来解决。

在此基础上，动态规划问题还有一些判断的'加分项'。

• 问题包含最大（小）或最多（少）等最优化描述。
• 问题的状态能够使用一个列表、多维矩阵或树来表示，并且一个状态与其周围的状态存在递推关系。

相应地，也存在一些'减分项'。

• 问题的目标是找出所有可能的解决方案，而不是找出最优解。
• 问题描述中有明显的排列组合的特征，需要返回具体的多个方案。

如果一个问题满足决策树模型，并具有较为明显的'加分项'，我们就可以假设它是一个动态规划问题，并在求解过程中验证它。

4.2 问题求解步骤

动态规划解题通常遵循以下基本步骤：描述决策，定义状态，建立 dp 表，推导状态转移方程，确定边界条件等。

此处用一个经典问题'最小路径和'来举例，体现解题步骤。

问题 给定一个 n * m 的二维网格 grid，网格中的每个单元格包含一个非负整数，表示该单元格的代价。机器人以左上角单元格为起始点，每次只能向下或者向右移动一步，直至到达右下角单元格。请返回从左上角到右下角的最小路径和。

Step 1：思考每轮的决策，定义状态，从而得到 dp 表 本题的每一轮的决策就是从当前格子向下或向右走一步。设当前格子的行列索引为 [i, j]，则向下或向右走一步后，索引变为 [i + 1, j] 或 [i, j + 1]。因此，状态应包含行索引和列索引两个变量，记为 dp[i, j]。

状态 [i, j] 对应的子问题为：从起始点 [0, 0] 走到 [i, j] 的最小路径和，解记为 dp[i, j]。

至此，我们就得到了二维 dp 矩阵，尺寸和输入网格 grid 相同。

Note 动态规划和回溯过程可以描述为一个决策序列，而状态由所有决策变量构成。它应当包含描述解题进度的所有变量，其包含了足够的信息，能够用来推导出下一个状态。

每个状态都对应一个子问题，我们会定义一个 dp 表来存储所有子问题的解，状态的每个独立变量都是 dp 表的一个维度。从本质上看，dp 表是状态和子问题的解之间的映射。

Step 2：找出最优子结构，进而推导出状态转移方程 对于状态 [i, j]，它只能从上边格子 [i - 1, j] 和左边格子 [i, j - 1] 转移而来。因此最优子结构为：到达 [i, j] 的最小路径和由 [i - 1, j] 的最小路径和与 [i, j - 1] 的最小路径和中较小的那一个决定。

根据分析出来的状态转移方程为： dp[i, j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]

Note 根据定义好的 dp 表，思考原问题和子问题的关系，找出通过子问题的最优解来构造原问题的最优解的方法，即最优子结构。

一旦我们找到了最优子结构，就可以使用它来构建出状态转移方程。

Step 3：确定边界条件和状态转移顺序

在本题中，处在首行的状态只能从其左边的状态得来，处在首列的状态只能从其上边的状态得来，因此首行 i = 0 和首列 j = 0 是边界条件。

由于每个格子是由其左方格子和上方格子转移而来，因此我们使用循环来遍历矩阵，外循环遍历各行，内循环遍历各列。

Note 边界条件在动态规划中用于初始化 dp 表，在搜索中用于剪枝。

状态转移顺序的核心是要保证在计算当前问题的解时，所有它依赖的更小子问题的解都已经被正确地计算出来。

4.2.1 暴力搜索

从状态 [i, j] 开始搜索，不断分解为更小的状态 [i - 1, 1] 和 [i, j - 1]，递归函数包括以下要素。

• 递归参数：状态 [i, j]。
• 返回值：从 [0, 0] 到 [i, j] 的最小路径和 dp[i, j]。
• 终止条件：当 i= 0 且 j = 0 时，返回代价 grid[0][0]。
• 剪枝：当 i < 0 时或 j < 0 时索引越界，此时返回代价 +∞，代表不可行。

实现代码如下：

#include <iostream>
using namespace std;
#include <vector>
#include <climits>

int minPathSumDFS(vector<vector<int>>& grid, int i, int j) {
    // 若为左上角单元格，则终止搜索
    if (i == 0 && j == 0) { return grid[0][0]; }
    // 若行列索引越界，则返回 +∞ 代价
    if (i < 0 || j < 0) { return INT_MAX; }
    // 计算从左上角到 (i-1, j) 和 (i, j-1) 的最小路径代价
    int up = minPathSumDFS(grid, i - 1, j);
    int left = minPathSumDFS(grid, i, j - 1);
    // 返回从左上角到 (i, j) 的最小路径代价
    return min(up, left) != INT_MAX ? min(up, left) + grid[i][j] : INT_MAX;
}

int main() {
    vector<vector<int>> grid = {{1, 3, 1, 5}, {2, 2, 4, 2}, {5, 3, 2, 1}, {4, 3, 5, 2}};
    int n = grid.size(), m = grid[0].size();
    cout << minPathSumDFS(grid, n - 1, m - 1);
    return 0;
}

4.2.2 记忆化搜索

我们引入一个和网格 grid 相同尺寸的记忆列表 mem，用于记录各个子问题的解，并将重叠子问题进行剪枝。

代码实现如下：

#include <iostream>
using namespace std;
#include <vector>
#include <climits>

int minPathSumDFS(vector<vector<int>>& grid, vector<vector<int>>& mem, int i, int j) {
    if (i == 0 && j == 0) { return grid[0][0]; }
    if (i < 0 || j < 0) { return INT_MAX; }
    // 若已有记录，则直接返回
    if (mem[i][j] != -1) { return mem[i][j]; }
    int up = minPathSumDFS(grid, mem, i - 1, j);
    int left = minPathSumDFS(grid, mem, i, j - 1);
    mem[i][j] = min(left, up) != INT_MAX ? min(left, up) + grid[i][j] : INT_MAX;
    return mem[i][j];
}

int main() {
    vector<vector<int>> grid = {{1, 3, 1, 5}, {2, 2, 4, 2}, {5, 3, 2, 1}, {4, 3, 5, 2}};
    int n = grid.size(), m = grid[0].size();
    vector<vector<int>> mem(n, vector<int>(m, -1));
    cout << minPathSumDFS(grid, mem, n - 1, m - 1);
    return 0;
}

在引入记忆化后，所有子问题的解只需计算一次，因此时间复杂度取决于状态总数，即网格尺寸 O(nm)。

4.2.3 动态规划

代码实现如下：

#include <iostream>
using namespace std;
#include <vector>

int minPathSumDP(vector<vector<int>>& grid) {
    int n = grid.size(), m = grid[0].size();
    vector<vector<int>> dp(n, vector<int>(m, 0));
    // 初始化 dp 表
    dp[0][0] = grid[0][0];
    // 状态转移：首行
    for (int j = 1; j < m; j++) { dp[0][j] = dp[0][j - 1] + grid[0][j]; }
    // 状态转移：首列
    for (int i = 1; i < n; i++) { dp[i][0] = dp[i - 1][0] + grid[i][0]; }
    // 状态转移：其余行和列
    for (int i = 1; i < n; i++) {
        for (int j = 1; j < m; j++) {
            dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
        }
    }
    return dp[n - 1][m - 1];
}

int main() {
    vector<vector<int>> grid = {{1, 3, 1, 5}, {2, 2, 4, 2}, {5, 3, 2, 1}, {4, 3, 5, 2}};
    cout << minPathSumDP(grid) << endl;
    return 0;
}

复杂度 时间复杂度为 O(nm)。** 数组 dp 大小为 n × m，因此空间复杂度为 O(nm)。

4.2.4 DP 空间优化

由于每个格子只与其左边和上边的格子有关，因此我们可以只用一个单行数组来实现 dp 表。

请注意，因为数组 dp 只能表示一行的状态，所以我们无法提前初始化首列状态，而是在遍历每行时更新它。

代码实现如下：

#include <iostream>
using namespace std;
#include <vector>

int minPathSumDP_Advance(vector<vector<int>>& grid) {
    int n = grid.size(), m = grid[0].size();
    vector<int> dp(m);
    // 初始化 dp 表
    dp[0] = grid[0][0];
    // 状态转移：首行
    for (int j = 1; j < m; j++) { dp[j] = dp[j - 1] + grid[0][j]; }
    // 状态转移：其余行
    for (int i = 1; i < n; i++) {
        // 状态转移：首列
        dp[0] = dp[0] + grid[i][0];
        // 状态转移：其余列
        for (int j = 1; j < m; j++) {
            // 此处的 dp[j] 对应没更新的，刚好为该次的 up 值
            dp[j] = min(dp[j - 1], dp[j]) + grid[i][j];
        }
    }
    return dp[m - 1];
}

int main() {
    vector<vector<int>> grid = {{1, 3, 1, 5}, {2, 2, 4, 2}, {5, 3, 2, 1}, {4, 3, 5, 2}};
    cout << minPathSumDP_Advance(grid) << endl;
    return 0;
}

5. 0-1 背包问题

我们引入一个例题来解决 0-1 背包问题。

Question 给定 n 个物品，第 i 个物品的重量为 wgt[i - 1]、价值为 val[i - 1]，和一个容量为 cap 的背包。每个物品只能选择一次，问在限定背包容量下能放入物品的最大价值。

0-1 背包问题可以视为一个多轮决策过程，每个物品都有'选或不选'两种状态，满足决策树模型，其目标是在容量约束下实现价值最大化，因此适合使用动态规划求解。

-Step1： 思考每轮的决策，定义状态，从而得到 dp 表

对于每个物品来说，不放入背包，背包容量不变；放入背包，背包容量减小。由此可得状态定义：当前物品编号 i 和背包容量 c，记为 [i, c]。

状态 [i, c] 对应的子问题为：前 i 个物品在容量为 c 的背包中的最大价值，记为 dp[i, c]。

待求解的是 dp[n, cap]，因此需要一个尺寸为 (n + 1)*(cap + 1) 的二维 dp 表。

-Step2： 找出最优子结构，进而推导出状态转移方程 当我们做出物品 i 的决策后，剩余的是前 i - 1 个物品决策的子问题，可分为以下两种情况。

• 不放入物品 i： 背包容量不变，状态变化为 [i - 1, c]。
• 放入物品 i： 背包容量减少 wgt[i - 1]，价值增加 val[i - 1]，状态变化为 [i - 1, c - wgt[i - 1]]。

上述分析向我们揭示了本题的最优子结构：最大价值 dp[i, c] 等于不放入物品 i 和放入物品 i 两种方案中价值更大的那一个。由此可推导出状态转移方程： dp[i, c] = max(dp[i - 1, c], dp[i - 1, c - wgt[i - 1]] + val[i - 1])

需要注意的是， 若当前物品重量 wgt[i - 1] 超出剩余背包容量 c，则只能选择不放入背包。

-Step3： 确定边界条件和状态转移顺序 当无物品或背包容量为 0 时最大价值为 0，即首列 dp[i, 0] 和首行 dp[0, c] 都等于 0。

当前状态 [i, c] 从上方的状态 [i - 1, c] 和左上方的状态 [i - 1, c - wgt[i - 1]] 转移而来，因此通过两层循环正序遍历整个 dp 表即可。

根据以上分析，我们接下来按顺序实现暴力搜索、记忆化搜索、动态规划解法。

5.1 暴力搜索

搜索代码包含以下要素。

• 递归参数：状态 [i, c]。
• 返回值：子问题的解 dp[i, c]。
• 终止条件：当物品编号越界 i = 0 或背包剩余容量为 c = 0 时，终止递归并返回价值 0。
• 剪枝：若当前物品重量超出背包剩余容量，则只能选择不放入背包。

代码实现如下：

#include <iostream>
using namespace std;
#include <vector>

int knapsackDFS(vector<int>& wgt, vector<int>& val, int i, int c) {
    // 若已选完所有物品或背包无剩余容量，则返回价值 0
    if (i == 0 || c == 0) { return 0; }
    // 若超过背包容量，则只能选择不放入背包
    if (wgt[i - 1] > c) { return knapsackDFS(wgt, val, i - 1, c); }
    // 计算不放入和放入物品 i 的最大价值
    int no = knapsackDFS(wgt, val, i - 1, c);
    int yes = knapsackDFS(wgt, val, i - 1, c - wgt[i - 1]) + val[i - 1];
    // 返回两种方案中价值更大的那一个
    return max(no, yes);
}

int main() {
    vector<int> wgt = {10, 20, 30, 40, 50};
    vector<int> val = {50, 120, 150, 210, 240};
    int cap = 50;
    int n = wgt.size();
    cout << "不超过背包容量的最大物品价值为：" << endl;
    cout << knapsackDFS(wgt, val, n, cap) << endl;
    return 0;
}

时间复杂度：O(2ⁿ)，因为每个物品都会产生不选和选两条搜索分支。

缺点 在递归树中会存在重叠子问题，并且当物品较多、背包容量较大，尤其是相同重量的物品较多时，重叠子问题的数量将会大幅增多。

5.2 记忆化搜索

为了保证重叠子问题只被计算一次，我们借助记忆列表 mem 来记录子问题的解，其中 mem[i][c] 对应 dp[i, c]。

代码实现如下：

#include <iostream>
using namespace std;
#include <vector>

int knapsackDFSMem(vector<int>& wgt, vector<int>& val, vector<vector<int>>& mem, int i, int c) {
    // 若已选完所有物品或背包无剩余容量，则返回价值 0
    if (i == 0 || c == 0) { return 0; }
    // 若超过背包容量，则只能选择不放入背包
    if (wgt[i - 1] > c) { return knapsackDFSMem(wgt, val, mem, i - 1, c); }
    // 若已有记录，则直接返回
    if (mem[i][c] != -1) { return mem[i][c]; }
    // 计算不放入和放入物品 i 的最大价值
    int no = knapsackDFSMem(wgt, val, mem, i - 1, c);
    int yes = knapsackDFSMem(wgt, val, mem, i - 1, c - wgt[i - 1]) + val[i - 1];
    // 记录并返回两种方案中价值更大的那一个
    mem[i][c] = max(yes, no);
    return mem[i][c];
}

int main() {
    vector<int> wgt = {10, 20, 30, 40, 50};
    vector<int> val = {50, 120, 150, 210, 240};
    int cap = 50;
    int n = wgt.size();
    vector<vector<int>> mem(n + 1, vector<int>(cap + 1, -1));
    cout << "不超过背包容量的最大物品价值为：";
    cout << knapsackDFSMem(wgt, val, mem, n, cap) << endl;
    return 0;
}

时间复杂度：O(n * cap)，因为引入记忆化之后，时间复杂度取决于子问题数量。

为什么要让 mem 数组所有初始化为 -1？ 答：mem 初始值必须用一个'不可能成为合法答案的值'（如 -1），不能用 0，因为 0 本身就是一个合法结果可以为最优解。

5.3 动态规划

动态规划实质上就是在状态转移中填充 dp 表的过程。

代码实现如下：

#include <iostream>
using namespace std;
#include <vector>

int knapsackDP(vector<int>& wgt, vector<int>& val, int cap) {
    int n = wgt.size();
    // 初始化 dp 表
    vector<vector<int>> dp(n + 1, vector<int>(cap + 1, 0));
    // 状态转移
    for (int i = 1; i <= n; i++) {
        for (int c = 1; c <= cap; c++) {
            if (wgt[i - 1] > c) {
                // 若超过背包容量，则不选物品 i
                dp[i][c] = dp[i - 1][c];
            } else {
                // 不选和选物品 i 这两种方案的较大值
                dp[i][c] = max(dp[i - 1][c], dp[i - 1][c - wgt[i - 1]] + val[i - 1]);
            }
        }
    }
    return dp[n][cap];
}

int main() {
    vector<int> wgt = {10, 20, 30, 40, 50};
    vector<int> val = {50, 120, 150, 210, 240};
    int cap = 50;
    int n = wgt.size();
    cout << "不超过背包容量的最大物品价值为：";
    cout << knapsackDP(wgt, val, cap) << endl;
    return 0;
}

时间复杂度和空间复杂度都由数组 dp 大小决定，即 O(n * cap)。

5.4 DP 空间优化（单数组空间优化）

由我们之前分析可知，每个状态都是由正上方或左上方的格子转移过来的。假设只有一个数组，当开始遍历第 i 行时，该数组存储的仍然是第 i - 1 行的状态。

• 如果采取正序遍历，那么遍历到 dp[i, j] 时，左上方 dp[i - 1, 1] ~ dp[i - 1, j - 1] 值可能已经被覆盖，此时就无法得到正确的状态转移结果。
• 如果采取倒序遍历，则不会发生覆盖问题，状态转移可以正确进行。

代码实现如下：

#include <iostream>
using namespace std;
#include <vector>

int knapsackDPComp(vector<int>& wgt, vector<int>& val, int cap) {
    int n = wgt.size();
    // 初始化 dp 表
    vector<int> dp(cap + 1, 0);
    // 状态转移
    for (int i = 1; i <= n; i++) {
        // 倒序遍历
        for (int c = cap; c >= 1; c--) {
            if (wgt[i - 1] <= c) {
                // 不选和选物品 i 这两种方案的较大值
                dp[c] = max(dp[c], dp[c - wgt[i - 1]] + val[i - 1]);
            }
        }
    }
    return dp[cap];
}

int main() {
    vector<int> wgt = {10, 20, 30, 40, 50};
    vector<int> val = {50, 120, 150, 210, 240};
    int cap = 50;
    int n = wgt.size();
    cout << "不超过背包容量的最大物品价值为：";
    cout << knapsackDPComp(wgt, val, cap) << endl;
    return 0;
}

6. 完全背包问题

我们引入一个例题来解决完全背包问题。

Question 给定 n 个物品，第 i 个物品的重量为 wgt[i - 1]、价值为 val[i - 1]，和一个容量为 cap 的背包。每个物品可以重复选取， 问在限定背包容量下能放入物品的最大价值。

通过分析题目我们发现：完全背包问题和 0-1 背包问题非常相似，区别仅在于不限制物品的选择次数， 也就是在完全背包问题中，每种物品的数量是无限的，因此将物品 i 放入背包后，仍可以从前 i 个物品中选择，而 0-1 背包只能从前 i - 1 个物品中选择。

在完全背包问题的规定下，状态 [i, c] 的变化分为两种情况。

• 不放入物品 i：与 0-1 背包问题相同，转移至 [i - 1, c]
• 放入物品 i：与 0-1 背包问题不同，转移至 [i, c - wgt[i - 1]]。

从而状态转移方程变为： dp[i, c] = max(dp[i - 1, c], dp[i, c - wgt[i - 1]] + val[i - 1])

代码实现如下：

#include <iostream>
using namespace std;
#include <vector>

int unboundedKnapsackDP(vector<int>& wgt, vector<int>& val, int cap) {
    int n = wgt.size();
    // 初始化 dp 表
    vector<vector<int>> dp(n + 1, vector<int>(cap + 1, 0));
    // 状态转移
    for (int i = 1; i <= n; i++) {
        for (int c = 1; c <= cap; c++) {
            if (wgt[i - 1] > c) {
                // 若超过背包容量，则不选物品 i
                dp[i][c] = dp[i - 1][c];
            } else {
                // 不选和选物品 i 这两种方案的较大值
                dp[i][c] = max(dp[i - 1][c], dp[i][c - wgt[i - 1]] + val[i - 1]);
            }
        }
    }
    return dp[n][cap];
}

int main() {
    vector<int> wgt = {1, 2, 3};
    vector<int> val = {5, 11, 15};
    int cap = 4;
    cout << "不超过背包容量的最大物品价值为：" << unboundedKnapsackDP(wgt, val, cap) << endl;
    return 0;
}

6.1 完全背包空间优化

由于当前状态是从左边和上边的状态转移而来的，因此空间优化后应该对 dp 表中的每一行进行正序遍历， 区别于 0-1 背包的倒序遍历。

代码实现如下：

#include <iostream>
using namespace std;
#include <vector>

int unboundedKnapsackDPComp(vector<int>& wgt, vector<int>& val, int cap) {
    int n = wgt.size();
    // 初始化 dp 表
    vector<int> dp(cap + 1, 0);
    // 状态转移
    for (int i = 1; i <= n; i++) {
        for (int c = 1; c <= cap; c++) {
            if (wgt[i - 1] > c) {
                // 若超过背包容量，则不选物品 i
                dp[c] = dp[c];
            } else {
                // 不选和选物品 i 这两种方案的较大值
                dp[c] = max(dp[c], dp[c - wgt[i - 1]] + val[i - 1]);
            }
        }
    }
    return dp[cap];
}

int main() {
    vector<int> wgt = {1, 2, 3};
    vector<int> val = {5, 11, 15};
    int cap = 4;
    cout << "不超过背包容量的最大物品价值为：" << unboundedKnapsackDPComp(wgt, val, cap) << endl;
    return 0;
}

6.2 零钱兑换问题

零钱兑换问题也是背包问题的一种变种问题，这里我们也用一个问题来引出这个知识点。

Question 给定 n 种硬币，第 i 种硬币的面值为 coins[i - 1]，目标金额为 amt，每种硬币可以重复选取，问能够凑出目标金额的最少硬币数量。如果无法凑出目标金额，则返回 -1。

思路 零钱兑换可以看作完全背包问题的一种特殊情况，两者具有以下联系与不同点。

• 两道题可以相互转换，'物品'对应'硬币'、'物品重量'对应'硬币面值'、'背包容量'对应'目标金额'。
• 优化目标相反，完全背包问题是要最大化物品价值，零钱兑换问题是要最小化硬币数量。
• 完全背包问题是求'不超过'背包容量下的解，零钱兑换是求'恰好'凑到目标金额的解。

-Step 1： 思考每轮的决策，定义状态，从而得到 dp 表 状态 [i, a] 对应的子问题为：前 i 种硬币能够凑出金额 a 的最少硬币数量，记为 dp[i, a]。 二维 dp 表的尺寸为 (n + 1) * (amt + 1)。

-Step 2： 找出最优子结构，进而推导出状态转移方程 本题与完全背包问题的状态转移方程存在以下两点差异。

• 本题要求最小值，因此需将运算符 max() 更改为 min()。
• 优化主体是硬币数量而非商品价值，因此在选中硬币时执行 + 1 即可。

dp[i, a] = min(dp[i - 1, a], dp[i, a - coins[i - 1]] + 1)

-Step 3： 确定边界条件和状态转移顺序 当目标金额为 0 时，凑出它的最少硬币数量为 0，即首列所有 dp[i, 0] 都等于 0。

当无硬币时，无法凑出任意 > 0 的目标金额，即是无效解。为使状态转移方程中的 min() 函数能够识别并过滤无效解，我们考虑使用 +∞ 来表示它们，即令首行所有 dp[0, a] 都等于 +∞。

对于 dp[0][0] 应该为 0，因为 0 个硬币就凑出了金额 0。

大多数编程语言并未提供 +∞ 变量，只能使用整型 int 的最大值来代替。而这又会导致大数越界：状态转移方程中的 +1 操作可能发生溢出。

为此，我们采用数字 amt + 1 来表示无效解，因为凑出 amt 的硬币数量最多为 amt。最后返回前，判断 dp[n, amt] 是否等于 amt + 1，若是则返回 -1，代表无法凑出目标金额。

代码实现如下：

#include <iostream>
using namespace std;
#include <vector>

int coinChangeDP(vector<int>& coins, int amt) {
    int n = coins.size();
    int MAX = amt + 1;
    // 初始化 dp 表
    vector<vector<int>> dp(n + 1, vector<int>(amt + 1, 0));
    // 状态转移：首行首列
    for (int a = 1; a <= amt; a++) { dp[0][a] = MAX; }
    // 状态转移：其余行和列
    for (int i = 1; i <= n; i++) {
        for (int a = 1; a <= amt; a++) {
            if (coins[i - 1] > a) {
                // 若超过目标金额，则不选硬币 i
                dp[i][a] = dp[i - 1][a];
            } else {
                // 不选和选硬币 i 这两种方案的较小值
                dp[i][a] = min(dp[i - 1][a], dp[i][a - coins[i - 1]] + 1);
            }
        }
    }
    return dp[n][amt] != MAX ? dp[n][amt] : -1;
}

int main() {
    vector<int> coins = {1, 2, 5};
    int amt = 4;
    cout << "凑到目标金额所需的最少硬币数量为：" << coinChangeDP(coins, amt) << endl;
    return 0;
}

6.2.1 空间优化

零钱兑换的空间优化的处理方式和完全背包问题一致：

#include <iostream>
using namespace std;
#include <vector>

int coinChangeDPComp(vector<int>& coins, int amt) {
    int n = coins.size();
    int MAX = amt + 1;
    // 初始化 dp 表
    vector<int> dp(amt + 1, MAX);
    dp[0] = 0;
    // 状态转移
    for (int i = 1; i <= n; i++) {
        for (int a = 1; a <= amt; a++) {
            if (coins[i - 1] > a) {
                // 若超过目标金额，则不选硬币 i
                dp[a] = dp[a];
            } else {
                // 不选和选硬币 i 这两种方案的较小值
                dp[a] = min(dp[a], dp[a - coins[i - 1]] + 1);
            }
        }
    }
    return dp[amt] != MAX ? dp[amt] : -1;
}

int main() {
    vector<int> coins = {1, 2, 5};
    int amt = 4;
    cout << "凑到目标金额所需的最少硬币数量为：" << coinChangeDPComp(coins, amt) << endl;
    return 0;
}

6.3 零钱兑换问题 II

我们继续引入一个问题。

Question 给定 n 种硬币，第 i 种硬币的面值为 coins[i - 1]，目标金额为 amt，每种硬币可以重复选取，问凑出目标金额的硬币组合数量。

思路 相比于上一题，本题目标是求组合数量，因此子问题变为：前 i 种硬币能够凑出金额 a 的组合数量。 而 dp 表仍然是尺寸为 (n + 1) * (amt + 1) 的二维矩阵。

当前状态的组合数量等于不选当前硬币与选当前硬币这两种决策的组合数量之和。状态转移方程为： dp[i, a] = dp[i - 1, a] + dp[i, a - coins[i - 1]]

当目标金额为 0 时，无须选择任何硬币即可凑出目标金额，因此应将首列所有 dp[i, 0] 都初始化为 1。当无硬币时，无法凑出任何 > 0 的目标金额，因此首行所有 dp[0, a] 都等于 0。

代码实现如下：

#include <iostream>
using namespace std;
#include <vector>

int coinChangeIIDP(vector<int>& coins, int amt) {
    int n = coins.size();
    // 初始化 dp 表
    vector<vector<int>> dp(n + 1, vector<int>(amt + 1, 0));
    // 初始化首列
    for (int i = 0; i <= n; i++) { dp[i][0] = 1; }
    // 状态转移
    for (int i = 1; i <= n; i++) {
        for (int a = 1; a <= amt; a++) {
            if (coins[i - 1] > a) {
                // 若超过目标金额，则不选硬币 i
                dp[i][a] = dp[i - 1][a];
            } else {
                // 不选和选硬币 i 这两种方案之和
                dp[i][a] = dp[i - 1][a] + dp[i][a - coins[i - 1]];
            }
        }
    }
    return dp[n][amt];
}

int main() {
    vector<int> coins = {1, 2, 5};
    int amt = 5;
    cout << "凑出目标金额的硬币组合数量为：" << coinChangeIIDP(coins, amt) << endl;
    return 0;
}

6.3.1 空间优化

空间优化处理方式与之前相同，代码实现如下：

#include <iostream>
using namespace std;
#include <vector>

int coinChangeIIDPComp(vector<int>& coins, int amt) {
    int n = coins.size();
    // 初始化 dp 表
    vector<int> dp(amt + 1, 0);
    dp[0] = 1;
    // 状态转移
    for (int i = 1; i <= n; i++) {
        for (int a = 1; a <= amt; a++) {
            if (coins[i - 1] > a) {
                // 若超过目标金额，则不选硬币 i
                dp[a] = dp[a];
            } else {
                // 不选和选硬币 i 这两种方案之和
                dp[a] = dp[a] + dp[a - coins[i - 1]];
            }
        }
    }
    return dp[amt];
}

int main() {
    vector<int> coins = {1, 2, 5};
    int amt = 5;
    cout << "凑出目标金额的硬币组合数量为：" << coinChangeIIDPComp(coins, amt) << endl;
    return 0;
}

7. 编辑距离问题

编辑距离（Levenshtein 距离）是两个字符串互相转换所需的最少操作次数，常用于衡量序列相似度。

我们引入一个例题来理解这个问题：

Question 输入两个字符串 s 和 t，返回将 s 转换为 t 所需的最少编辑步数。 你可以在一个字符串中进行三种编辑操作：插入一个字符、删除一个字符、将字符替换为任意一个字符。

7.1 暴力搜索

首先我们试试直接暴力求解来获取思路

#include <iostream>
using namespace std;
#include <vector>
#include <string>

int editDistanceDFS(string s, string t, int i, int j) {
    // 若 s 和 t 都为空，则返回 0
    if (i == 0 && j == 0) { return 0; }
    // 若 s 为空，则返回 t 长度
    if (i == 0) { return j; }
    // 若 t 为空，则返回 s 长度
    if (j == 0) { return i; }
    // 若两字符相等，则直接跳过此两字符
    if (s[i - 1] == t[j - 1]) { return editDistanceDFS(s, t, i - 1, j - 1); }
    // 最少编辑步数 = 插入、删除、替换这三种操作的最少编辑步数 + 1
    int insertMt = editDistanceDFS(s, t, i, j - 1);
    int deleteMt = editDistanceDFS(s, t, i - 1, j);
    int replaceMt = editDistanceDFS(s, t, i - 1, j - 1);
    // 返回最少编辑步数
    return min(min(insertMt, deleteMt), replaceMt) + 1;
}

int main() {
    string s = "bag";
    string t = "pack";
    int n = s.length(), m = t.length();
    cout << "将 " << s << " 更改为 " << t << " 最少需要编辑 " << editDistanceDFS(s, t, n, m) << " 步\n";
    return 0;
}

7.2 记忆化搜索

当然可以加一个 mem 数组来记忆子问题的解，避免重叠子问题被重复计算。

#include <iostream>
using namespace std;
#include <vector>
#include <string>

int editDistanceDFSMem(string s, string t, vector<vector<int>>& mem, int i, int j) {
    // 若 s 和 t 都为空，则返回 0
    if (i == 0 && j == 0) { return 0; }
    // 若已有记录，则直接返回之
    if (mem[i][j] != -1) { return mem[i][j]; }
    // 若 s 为空，则返回 t 长度
    if (i == 0) { return j; }
    // 若 t 为空，则返回 s 长度
    if (j == 0) { return i; }
    // 若两字符相等，则直接跳过此两字符
    if (s[i - 1] == t[j - 1]) { return editDistanceDFSMem(s, t, mem, i - 1, j - 1); }
    // 最少编辑步数 = 插入、删除、替换这三种操作的最少编辑步数 + 1
    int insertMt = editDistanceDFSMem(s, t, mem, i, j - 1);
    int deleteMt = editDistanceDFSMem(s, t, mem, i - 1, j);
    int replaceMt = editDistanceDFSMem(s, t, mem, i - 1, j - 1);
    // 记录并返回最少编辑步数
    mem[i][j] = min(min(insertMt, deleteMt), replaceMt) + 1;
    return mem[i][j];
}

int main() {
    string s = "bag";
    string t = "pack";
    int n = s.length(), m = t.length();
    vector<vector<int>> mem(n + 1, vector<int>(m + 1, -1));
    cout << "将 " << s << " 更改为 " << t << " 最少需要编辑 " << editDistanceDFSMem(s, t, mem, n, m) << " 步\n";
    return 0;
}

为何 mem 初始化为 -1？ 答：因为 0 本身是一个合法且常见的答案，所以不能用 0 来表示'没算过'，只能用 -1 这种不可能成为答案的值作为标记。

7.3 动态规划

编辑距离问题可以很自然地用决策树模型来解释。 字符串对应树节点，一轮决策（一次编辑操作）对应树的一条边。

动态规划的思路

-Step 1： 思考每轮的决策，定义状态，从而得到 dp 表 每一轮的决策是对字符串 s 进行一次编辑操作。

我们希望在编辑操作的过程中，问题的规模逐渐缩小，这样才能构建子问题。设字符串 s 和 t 的长度分别为 n 和 m，我们先考虑两字符串尾部的字符 s[n - 1] 和 t[m - 1]。

• 若 s[n - 1] 和 t[m - 1] 相同，我们可以跳过它们，直接考虑 s[n - 2] 和 t[m - 2]。
• 若 s[n - 1] 和 t[m - 1] 不同，我们需要对 s 进行一次编辑（插入、删除、替换），使得两字符串尾部的字符相同，从而可以跳过它们，考虑规模更小的问题。

状态 [i, j] 对应的子问题：将 s 的前 i 个字符更改为 t 的前 j 个字符所需的最少编辑步数， 至此，得到一个尺寸为 (i + 1) * (j + 1) 的二维 dp 表。

-Step 2： 找出最优子结构，进而推导出状态转移方程

考虑子问题 dp[i, j]，其对应的两个字符串的尾部字符为 s[i - 1] 和 t[j - 1]，可根据不同编辑操作分为三种情况。

• 在 s[i - 1] 之后添加 t[j - 1]，则剩余子问题 dp[i, j - 1]。
• 删除 s[i - 1]，则剩余子问题 dp[i - 1, j]。
• 将 s[i - 1] 替换为 t[i - 1]，则剩余子问题 dp[i - 1, j - 1]。

根据以上分析，可得最优子结构：dp[i, j] 的最少编辑步数等于 dp[i, j - 1]、dp[i - 1, j]、dp[i - 1, j - 1] 三者中的最少编辑步数，再加上本次的编辑步数 1。对应的状态转移方程为： dp[i, j] = min(dp[i, j - 1], dp[i - 1, j], dp[i - 1, j - 1]) + 1

请注意，当 s[i - 1] 和 t[j - 1] 相同时，无须编辑当前字符，这种情况下的状态转移方程为： dp[i, j] = dp[i - 1, j - 1]

-Step 3： 确定边界条件和状态转移顺序

当两字符串都为空时，编辑步数为 0，即 dp[0, 0] = 0。当 s 为空但 t 不为空时，最少编辑步数等于 t 的长度，即首行 dp[0, j] = j。当 s 不为空但 t 为空时，最少编辑步数等于 s 的长度，即首列 dp[i, 0] = i。

观察状态转移方程，解 dp[i, j] 依赖左方、上方、左上方的解，因此通过两层循环正序遍历整个 dp 表即可。

代码实现如下：

#include <iostream>
using namespace std;
#include <vector>
#include <string>

int editDistanceDP(string s, string t) {
    int n = s.length(), m = t.length();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
    // 状态转移：首行首列
    for (int i = 1; i <= n; i++) { dp[i][0] = i; }
    for (int j = 1; j <= m; j++) { dp[0][j] = j; }
    // 状态转移：其余行和列
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (s[i - 1] == t[j - 1]) {
                // 若两字符相等，则直接跳过此两字符
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                // 最少编辑步数 = 插入、删除、替换这三种操作的最少编辑步数 + 1
                dp[i][j] = min(min(dp[i][j - 1], dp[i - 1][j]), dp[i - 1][j - 1]) + 1;
            }
        }
    }
    return dp[n][m];
}

int main() {
    string s = "bag";
    string t = "pack";
    int n = s.length(), m = t.length();
    cout << "将 " << s << " 更改为 " << t << " 最少需要编辑 " << editDistanceDP(s, t) << " 步\n";
    return 0;
}

7.4 DP 空间优化

由于 dp[i, j] 是由上方 dp[i - 1, j]、左方 dp[i, j - 1]、左上方 dp[i - 1, j - 1] 转移而来的，而正序遍历会丢失左上方 dp[i - 1, j - 1]，倒序遍历无法提前构建 dp[i, j - 1]，因此两种遍历顺序都不可取。

为此，我们可以使用一个变量 leftup 来暂存左上方的解 dp[i - 1, j - 1]，从而只需考虑左方和上方的解。此时的情况与完全背包问题相同，可使用正序遍历， 因为 dp[j] 仍然需要用到当前行的左边 dp[j-1]。

代码实现如下：

#include <iostream>
using namespace std;
#include <vector>
#include <string>

int editDistanceDPComp(string s, string t) {
    int n = s.length(), m = t.length();
    vector<int> dp(m + 1, 0);
    // 状态转移：首行
    for (int j = 1; j <= m; j++) { dp[j] = j; }
    // 状态转移：其余行
    for (int i = 1; i <= n; i++) {
        // 状态转移：首列
        int leftup = dp[0]; // 暂存 dp[i-1, j-1]
        dp[0] = i;
        // 状态转移：其余列
        for (int j = 1; j <= m; j++) {
            int temp = dp[j];
            if (s[i - 1] == t[j - 1]) {
                // 若两字符相等，则直接跳过此两字符
                dp[j] = leftup;
            } else {
                // 最少编辑步数 = 插入、删除、替换这三种操作的最少编辑步数 + 1
                dp[j] = min(min(dp[j - 1], dp[j]), leftup) + 1;
            }
            leftup = temp; // 更新为下一轮的 dp[i-1, j-1]
        }
    }
    return dp[m];
}

int main() {
    string s = "bag";
    string t = "pack";
    int n = s.length(), m = t.length();
    cout << "将 " << s << " 更改为 " << t << " 最少需要编辑 " << editDistanceDPComp(s, t) << " 步\n";
    return 0;
}

部分题目练习

以下是相关题目及参考题解，供学习。

（洛谷）P1255 数楼梯

此题主要考察的是 DP+ 高精度的使用

#include <iostream>
using namespace std;
#include <vector>

string add(string a, string b) {
    string res = "";
    int carry = 0;
    int i = a.size() - 1, j = b.size() - 1;
    // 没有加完或者还有进位则继续
    while (i >= 0 || j >= 0 || carry) {
        int x = (i >= 0) ? a[i--] - '0' : 0;
        int y = (j >= 0) ? b[j--] - '0' : 0;
        int sum = x + y + carry;
        // 字符串拼接
        res = char(sum % 10 + '0') + res;
        carry = sum / 10; // 进位保存
    }
    return res;
}

int main() {
    int n;
    cin >> n;
    vector<string> dp(n + 1);
    dp[1] = "1";
    dp[2] = "2";
    for (int i = 3; i <= n; i++) {
        dp[i] = add(dp[i - 1], dp[i - 2]);
    }
    cout << dp[n];
    return 0;
}

总结

• 高精度不是'特殊算法'，而是'当数太大时，用字符串模拟人工计算'。
• 其中 add() 这段代码不是技巧，也不是魔法，它只是把「小学竖式加法」一行一行翻译成了 C++ 代码。

（LeetCode）70. 爬楼梯

经典例题

解法一：使用记忆化搜索

class Solution {
public:
    int dfs(int n, vector<int>& mem) {
        if (n == 1 || n == 2) { return n; }
        if (mem[n] != -1) { return mem[n]; }
        int count = dfs(n - 1, mem) + dfs(n - 2, mem);
        mem[n] = count;
        return count;
    }
    int climbStairs(int n) {
        vector<int> mem(n + 1, -1);
        return dfs(n, mem);
    }
};

解法二：使用 DP 算法

class Solution {
public:
    int DPclimb(int n) {
        if (n == 1 || n == 2) { return n; }
        int a = 1;
        int b = 2;
        for (int i = 3; i <= n; i++) {
            int temp = b;
            b = a + b;
            a = temp;
        }
        return b;
    }
    int climbStairs(int n) {
        return DPclimb(n);
    }
};

（LeetCode）746. 使用最小花费爬楼梯

本题主要考察动态规划中的最优子结构特性，是一类典型的带代价的路径选择问题

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
        vector<int> dp(n + 1);
        dp[0] = 0;
        dp[1] = 0;
        for (int i = 2; i <= n; i++) {
            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }
        return dp[n];
    }
};

部分 Q&A： Q1. 为什么这里的 dp[0] 和 dp[1] 不是分别等于 cost[0] 和 cost[1]？** 答：因为 dp[i] 表示'到达位置 i 的最小花费'，起点位置（0 和 1）尚未踩上任何台阶，不产生费用，因此 dp[0] = dp[1] = 0。

Q2. 为什么循环是到 cost.size() 大小结束？ 答：因为要到达顶部，刚好此处 cost.size() 表示台阶总数，在 DP 中将 dp[n] 作为楼顶位置，通过从底到顶的状态转移就可以算出 dp[n] 即登顶所需代价。

（LeetCode）64. 最小路径和

本题主要考察使用动态规划，dp[i][j] 表示到达 (i,j) 的最小路径和，通过比较上方和左方状态进行转移，最终得到右下角的最小路径和。

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        // 初始化 dp 表
        vector<vector<int>> dp(n, vector<int>(m, 0));
        dp[0][0] = grid[0][0];
        // 状态转移首行
        for (int j = 1; j < m; j++) { dp[0][j] = dp[0][j - 1] + grid[0][j]; }
        // 状态转移首列
        for (int i = 1; i < n; i++) { dp[i][0] = dp[i - 1][0] + grid[i][0]; }
        // 状态转移剩余行列
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }
        }
        return dp[n - 1][m - 1];
    }
};

（洛谷）P1048 [NOIP 2005 普及组] 采药

本题就是典型的 0-1 背包问题

解法一： 动态规划

#include <iostream>
using namespace std;
#include <vector>

int main() {
    int t, m;
    cin >> t >> m;
    int temp = m;
    vector<int> Atime;
    vector<int> vals;
    while (temp--) {
        int time, val;
        cin >> time >> val;
        Atime.push_back(time);
        vals.push_back(val);
    }
    // ------------- 以上为数据输入
    vector<vector<int>> dp(m + 1, vector<int>(t + 1, 0));
    for (int i = 1; i <= m; i++) {
        for (int c = 1; c <= t; c++) {
            if (Atime[i - 1] > c) { dp[i][c] = dp[i - 1][c]; }
            else { dp[i][c] = max(dp[i - 1][c], dp[i - 1][c - Atime[i - 1]] + vals[i - 1]); }
        }
    }
    cout << dp[m][t];
    return 0;
}

解法二： 使用一维 dp 空间优化

#include <iostream>
using namespace std;
#include <vector>

int main() {
    int t, m;
    cin >> t >> m;
    int temp = m;
    vector<int> Atime;
    vector<int> vals;
    while (temp--) {
        int time, val;
        cin >> time >> val;
        Atime.push_back(time);
        vals.push_back(val);
    }
    // ------------- 以上为数据输入
    vector<int> dp(t + 1);
    for (int i = 1; i <= m; i++) {
        for (int c = t; c >= 1; c--) {
            if (Atime[i - 1] <= c) { dp[c] = max(dp[c], dp[c - Atime[i - 1]] + vals[i - 1]); }
        }
    }
    cout << dp[t];
    return 0;
}

（洛谷）P1616 疯狂的采药

本题主要考察完全背包模型的理解与一维动态规划优化能力。

#include <iostream>
using namespace std;
#include <vector>

int main() {
    int t, m;
    cin >> t >> m;
    vector<int> Atimes;
    vector<int> AVals;
    int temp = m;
    while (temp--) {
        int a, b;
        cin >> a >> b;
        Atimes.push_back(a);
        AVals.push_back(b);
    }
    // ------------- 以上为数据输入
    vector<long long> dp(t + 1, 0);
    for (int i = 1; i <= m; i++) {
        for (int st = 1; st <= t; st++) {
            if (Atimes[i - 1] > st) { dp[st] = dp[st]; }
            else { dp[st] = max(dp[st], dp[st - Atimes[i - 1]] + AVals[i - 1]); }
        }
    }
    cout << dp[t];
    return 0;
}

注意 由于 m 的最大情况为 10^4，t 的最大情况为 10^7，那么最后的值就是 10^11，而 int 大约只有 10^9，所以会爆 int，我们得使用 long long 防止溢出，不然最后一个样例会过不了。

（LeetCode）72. 编辑距离

本题是经典的编辑距离模型，熟悉并理解原理

class Solution {
public:
    int minDistance(string word1, string word2) {
        int n = word1.length(), m = word2.length();
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
        // 初始化首行，首列
        for (int j = 1; j <= m; j++) { dp[0][j] = j; }
        for (int i = 1; i <= n; i++) { dp[i][0] = i; }
        // 处理其他行列
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (word1[i - 1] == word2[j - 1]) { dp[i][j] = dp[i - 1][j - 1]; }
                else { dp[i][j] = min(min(dp[i][j - 1], dp[i - 1][j]), dp[i - 1][j - 1]) + 1; }
            }
        }
        return dp[n][m];
    }
};

（LeetCode）322. 零钱兑换

本题与零钱兑换 I 题目一致，可拿来巩固思路

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int n = coins.size();
        int MAX = amount + 1;
        vector<vector<int>> dp(n + 1, vector<int>(amount + 1, 0));
        // 首行初始化
        for (int j = 0; j <= amount; j++) { dp[0][j] = MAX; }
        // 其余行状态转移
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= amount; j++) {
                if (coins[i - 1] > j) { dp[i][j] = dp[i - 1][j]; }
                else { dp[i][j] = min(dp[i - 1][j], dp[i][j - coins[i - 1]] + 1); }
            }
        }
        return dp[n][amount] != MAX ? dp[n][amount] : -1;
    }
};

空间优化

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int n = coins.size();
        int MAX = amount + 1;
        vector<int> dp(amount + 1, MAX);
        dp[0] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= amount; j++) {
                if (coins[i - 1] > j) { dp[j] = dp[j]; }
                else { dp[j] = min(dp[j], dp[j - coins[i - 1]] + 1); }
            }
        }
        return dp[amount] != MAX ? dp[amount] : -1;
    }
};