bitworld 的博客
【CSP-J初赛】动态规划（一）
bitworld 最强壮的男人 SU @ 2025-7-31 16:42:36

动态规划（一）

一、动态规划的核心思想

动态规划是一种通过将原问题分解为相对简单的、可重复的子问题来求解复杂问题的方法。它与分治法（Divide and Conquer）的关键区别在于，分治法处理的子问题通常是相互独立的，而动态规划处理的子问题是“重叠”的，一个子问题的解可能被多次使用。

为了避免重复计算这些重叠子问题，动态规划会系统性地记录下所有子问题的解。这种“记忆化”的策略是其效率的关键。

一个问题能够使用动态规划求解，通常需要满足两个核心性质：

最优子结构 (Optimal Substructure) 最优子结构意味着一个问题的最优解包含了其子问题的最优解。换句话说，我们可以通过组合子问题的最优解，来构造出原问题的最优解。例如，两点间的最短路径问题，如果 $A \to C \to B$ 是从 $A$ 到 $B$ 的最短路径，那么 $A \to C$ 也必然是从 $A$ 到 $C$ 的最短路径。
重叠子问题 (Overlapping Subproblems) 在问题的求解过程中，许多子问题的计算会被重复执行。递归求解时，这种重复计算会导致指数级的时间复杂度。动态规划通过一个表格（通常是数组）来存储已经计算过的子问题的解，每次需要解一个子问题时，先检查表格中是否已有答案，从而将计算次数从指数级降至多项式级。

1.1 两种实现

动态规划主要有两种实现方式：自顶向下（Top-Down）和自底向上（Bottom-Up）。

自顶向下与记忆化搜索 (Top-Down with Memoization) 这种方式从原问题出发，通过递归函数进行求解。当需要解决一个子问题时，函数首先检查是否已经计算过该子问题。如果是，则直接返回存储的结果；否则，进行计算，并将结果存入表格中，然后再返回。这种方法非常直观，其逻辑与纯粹的递归思考方式一致。
自底向上与递推 (Bottom-Up with Tabulation) 这种方式则完全避免了递归。它从最小的子问题开始，迭代地计算并填充DP表格。计算当前问题的解时，它所依赖的更小子问题的解都已经被计算并存储好了。这种方式通常在代码实现上效率更高，因为它避免了递归调用的开销。

对于笔试和竞赛而言，自底向上的递推法更为常见，因为它通常具有更好的常数性能。

二、动态规划的解题四要素

掌握动态规划的关键在于能够清晰地构建出递推模型。这可以分解为四个核心步骤：

定义状态 (State Definition) 这是最关键的一步。我们需要定义一个数组（如 $dp[i]$ 或 $dp[i][j]$ ），并明确其中每个元素代表的含义。状态的定义必须是无后效性的，即一旦某个状态的值确定了，它就不会再被后续的计算所改变。同时，这个状态定义需要能够覆盖原问题的所有子问题。例如， $dp[i]$ 可以表示“爬到第 $i$ 级台阶的总方法数”，或者“使用前 $i$ 个物品，在容量为 $j$ 的背包中能获得的最大价值”。
写出状态转移方程 (State Transition Equation) 这是算法的核心。状态转移方程描述了不同状态之间的数学关系。它定义了如何从一个或多个已知的子问题（较小规模的状态）的解，推导出当前问题（较大规模的状态）的解。例如，爬台阶问题中，要到第 $i$ 级台阶，可以从第 $i-1$ 级跨一步，或者从第 $i-2$ 级跨两步，所以 $dp[i] = dp[i-1] + dp[i-2]$ 。
确定初始化条件 (Initialization) 任何递推都需要一个起点。初始化就是为DP表格中的基础状态（通常是规模最小的子问题）赋上确定的值。这些基础状态是状态转移方程的递归终点。例如，在爬台阶问题中， $dp = 1$ （表示在第0级台阶，即原地不动，有1种方法）， $dp = 1$ （到第1级台阶只有1种方法）。
确定计算顺序与最终答案 (Calculation Order & Final Answer) 在自底向上的实现中，我们必须保证在计算一个状态 $dp[i]$ 时，它所依赖的所有状态（如 $dp[i-1]$ , $dp[i-2]$ ）都已经被计算出来了。这决定了我们代码中循环的遍历顺序。最后，我们需要明确原问题的解对应于DP表格中的哪个元素，例如 $dp[n]$ 或 $dp[N][M]$ 。

接下来，我们将通过几个经典的DP模型来具体阐述这四个要素的应用。

三、经典动态规划模型

3.1 线性DP

线性DP通常处理序列上的问题，其状态定义多为一维 $dp[i]$ 或二维 $dp[i][j]$ ，且状态转移通常是线性的。

示例1：斐波那契数列 / 爬台阶

题意概括: 假设你正在爬楼梯。需要 $n$ 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶？

1. 状态定义: $dp[i]$ 表示爬到第 $i$ 级台阶的总方法数。
2. 状态转移方程: 要到达第 $i$ 级台阶，最后一步有两种可能：
- 从第 $i-1$ 级台阶爬 1 步上来。方法数继承自 $dp[i-1]$ 。
- 从第 $i-2$ 级台阶爬 2 步上来。方法数继承自 $dp[i-2]$ 。因此，总方法数是两者之和：
$dp[i] = dp[i-1] + dp[i-2]$
3. 初始化:
- $dp[0] = 1$ （在起点，视为1种方法）。
- $dp[1] = 1$ （到第1阶只有1种方法：爬1步）。
4. 计算顺序与最终答案

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    if (n <= 1) {
        cout << 1 << endl;
        return 0;
    }
    vector<int> dp(n + 1);
    dp[0] = 1; // 初始化：在第0阶有1种方法
    dp[1] = 1; // 初始化：到第1阶有1种方法
    for (int i = 2; i <= n; ++i) {
        dp[i] = dp[i - 1] + dp[i - 2]; // 状态转移
    }
    cout << dp[n] << endl; // 最终答案
    return 0;
}

复杂度分析:
- 时间复杂度: $O(n)$ ，因为循环执行了 $n-1$ 次。
- 空间复杂度: $O(n)$ ，因为使用了一个大小为 $n+1$ 的dp数组。

示例2：最长递增子序列 (Longest Increasing Subsequence, LIS)

题意概括: 给定一个整数序列，找到其最长递增子序列的长度。子序列不要求连续。

1. 状态定义: $dp[i]$ 表示以第 $i$ 个元素 $a[i]$ 结尾的最长递增子序列的长度。这个定义非常关键，它确保了状态的唯一性和可转移性。
2. 状态转移方程: 对于每个元素 $a[i]$ ，我们需要找到在它之前的所有元素 $a[j]$ （其中 $j < i$ ）。如果 $a[j] < a[i]$ ，那么我们就可以将 $a[i]$ 接在以 $a[j]$ 结尾的递增子序列后面，形成一个新的、更长的递增子序列。我们要在所有可能的 $j$ 中选择能使新序列最长的那个。
$$dp[i] = \max_{0 \le j < i, a[j] < a[i]} \{dp[j]\} + 1 $$
如果找不到这样的 $j$ ，说明 $a[i]$ 只能自成一个序列，长度为1。
3. 初始化: 每个元素自身都可以构成一个长度为1的递增子序列，所以将所有 $dp[i]$ 初始化为1。
$dp[i] = 1 \quad \forall i \in [0, n-1]$
4. 计算顺序与最终答案: $i$ 从 0 到 $n-1$ 顺序计算。最终答案不是 $dp[n-1]$ ，因为最长递增子序列不一定以最后一个元素结尾。最终答案是整个 $dp$ 数组中的最大值。
$\text{Answer} = \max_{0 \le i < n} \{dp[i]\}$

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];

    if (n == 0) {
        cout << 0 << endl;
        return 0;
    }

    vector<int> dp(n, 1); // 初始化：所有dp[i]为1
    int ans = 1;
    for (int i = 1; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            if (a[j] < a[i]) {
                dp[i] = max(dp[i], dp[j] + 1); // 状态转移
            }
        }
        ans = max(ans, dp[i]); // 更新全局最长长度
    }
    cout << ans << endl; // 最终答案
    return 0;
}

复杂度分析:
- 时间复杂度: $O(n^2)$ ，因为有两层嵌套循环。
- 空间复杂度: $O(n)$ ，用于存储 $a$ 数组和 $dp$ 数组。

3.2 背包DP

背包问题是DP中的一个大家族，核心是选择物品放入背包以达到最优效果。

示例3：0/1背包问题

题意概括: 有 $N$ 件物品和一个容量为 $V$ 的背包。第 $i$ 件物品的重量是 $w[i]$ ，价值是 $v[i]$ 。求解将哪些物品装入背包，可使这些物品总重量不超过背包容量，且总价值最大。每种物品只有一件，要么放，要么不放。

1. 状态定义: $dp[j]$ 表示容量为 $j$ 的背包所能获得的最大总价值。
2. 状态转移方程: 对于第 $i$ 件物品，我们考虑是否要将它放入容量为 $j$ 的背包中。
- 不放: 如果不放第 $i$ 件物品，那么背包的价值与只考虑前 $i-1$ 件物品时一样，即 $dp[j]$ 不变。
- 放: 如果要放第 $i$ 件物品（前提是 $j \ge w[i]$ ），那么我们需要为它腾出 $w[i]$ 的空间。此时的价值等于“在放入这件物品前，容量为 $j-w[i]$ 的背包能达到的最大价值”加上这件物品自身的价值 $v[i]$ 。即 $dp[j-w[i]] + v[i]$ 。我们在“放”与“不放”之间做出最优选择：
$dp[j] = \max(dp[j], \quad dp[j - w[i]] + v[i])$
3. 初始化: $dp$ 数组所有元素初始化为0。
4. 计算顺序与最终答案: 我们需要遍历每一件物品，然后用这件物品去更新 $dp$ 数组。关键在于内层循环的遍历顺序。为了保证每个物品只被选择一次（0/1特性），内层循环必须从后向前遍历（从 $V$ 到 $w[i]$ ）。

为什么必须逆序？ 假设我们正序遍历。在计算 $dp[j]$ 时，我们用到了 $dp[j-w[i]]$ 。如果正序，此时的 $dp[j-w[i]]$ 可能已经是被第 $i$ 个物品更新过的了。这会导致第 $i$ 个物品被重复计算，问题就变成了完全背包。逆序遍历时，计算 $dp[j]$ 所依赖的 $dp[j-w[i]]$ 还是上一轮（处理第 $i-1$ 个物品时）的状态，保证了第 $i$ 个物品只用一次。

最终答案是 $dp[V]$ 。

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int N, V;
    cin >> N >> V;
    vector<int> w(N), v(N);
    for(int i = 0; i < N; ++i) cin >> w[i] >> v[i];

    vector<int> dp(V + 1, 0); // 初始化dp数组

    for (int i = 0; i < N; ++i) { // 遍历每个物品
        for (int j = V; j >= w[i]; --j) { // 逆序遍历背包容量
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]); // 状态转移
        }
    }

    cout << dp[V] << endl; // 最终答案
    return 0;
}

复杂度分析:
- 时间复杂度: $O(N \times V)$ 。
- 空间复杂度: $O(V)$ 。这是空间优化后的一维形式，原始的二维形式为 $O(N \times V)$ 。

3.3 区间DP

区间DP通常解决在一段连续区间上的最优问题。

示例4：石子合并

题意概括: 有 $N$ 堆石子排成一排，每堆石子的质量为 $m_i$ 。每次可以合并相邻的两堆石子，合并的代价为这两堆石子的质量之和。求将所有石子合并成一堆的最小总代价。

1. 状态定义: $dp[i][j]$ 表示合并区间 $[i, j]$ 内所有石子的最小代价。
2. 状态转移方程: 要合并区间 $[i, j]$ ，最后一步必然是把两个已经合并好的相邻子区间合并。我们可以枚举这个分割点 $k$ ( $i \le k < j$ ) 。区间 $[i, j]$ 最后一步是合并 $[i, k]$ 和 $[k+1, j]$ 这两堆。
- 合并 $[i, k]$ 的最小代价是 $dp[i][k]$ 。
- 合并 $[k+1, j]$ 的最小代价是 $dp[k+1][j]$ 。
- 将这两大堆合并的代价是区间 $[i, j]$ 的总质量，我们用前缀和 $S[i]$ 快速计算，即 $S[j] - S[i-1]$ 。
所以，对于一个分割点 $k$ ，总代价是 $dp[i][k] + dp[k+1][j] + (S[j] - S[i-1])$ 。我们需要遍历所有可能的 $k$ 来找到最小值。
$$dp[i][j] = \min_{i \le k < j} \{ dp[i][k] + dp[k+1][j] \} + \sum_{l=i}^{j} m_l $$
3. 初始化: $dp[i][i] = 0$ ，因为单个石子堆不需要合并，代价为0。其他 $dp[i][j]$ 初始化为一个极大值。
4. 计算顺序与最终答案: 区间DP的计算顺序很特殊。我们依赖的子问题 $dp[i][k]$ 和 $dp[k+1][j]$ 的区间长度都比 $dp[i][j]$ 的区间长度小。所以，我们应该按照区间长度从小到大的顺序来计算。
- 外层循环枚举区间长度 $len$ 从 2到 $N$ 。
- 内层循环枚举区间的左端点 $i$ 。
- 右端点 $j = i + len - 1$ 。
- 最内层循环枚举分割点 $k$ 。
最终答案是 $dp[N]$ (假设石子编号从1到N)。

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

const int INF = 1e9;

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    vector<int> m(n + 1);
    vector<int> s(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        cin >> m[i];
        s[i] = s[i - 1] + m[i]; // 计算前缀和
    }

    vector<vector<int>> dp(n + 1, vector<int>(n + 1, INF));

    for (int i = 1; i <= n; ++i) {
        dp[i][i] = 0; // 初始化
    }

    // len是区间长度
    for (int len = 2; len <= n; ++len) {
        // i是区间左端点
        for (int i = 1; i <= n - len + 1; ++i) {
            int j = i + len - 1; // j是区间右端点
            int cst = s[j] - s[i - 1]; // 当前合并代价
            // k是分割点
            for (int k = i; k < j; ++k) {
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + cst);
            }
        }
    }

    cout << dp[1][n] << endl; // 最终答案
    return 0;
}

复杂度分析:
- 时间复杂度: $O(n^3)$ ，因为有三层嵌套循环（长度、左端点、分割点）。
- 空间复杂度: $O(n^2)$ ，用于存储DP表和前缀和。

四、DP优化技巧：滚动数组

在很多DP问题中，计算当前状态 $dp[i]$ 仅仅依赖于前一个或前几个状态（如 $dp[i-1]$ 、 $dp[i-2]$ ）。这意味着我们无需存储整个DP表格，从而可以大幅度优化空间复杂度。这种技术被称为“滚动数组”。

以0/1背包问题为例，其二维状态转移方程是 $dp[i][j] = \max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])$。可以看到，计算第 $i$ 行时，我们只用到了第 $i-1$ 行的数据。因此，我们可以用一个一维数组来代替二维数组，也就是之前代码中展示的 $O(V)$ 空间复杂度的解法。这就是滚动数组思想的直接应用。

对于斐波那契数列 $dp[i] = dp[i-1] + dp[i-2]$ ，我们甚至只需要两个变量来存储前两个值，就可以计算出下一个值，空间复杂度可以优化到 $O(1)$ 。

五、练习

第一部分：选择题

下列哪个问题最适合使用动态规划来解决？ A. 在一个无权图中寻找两个节点之间的最短路径。 B. 对一个数组进行快速排序。 C. 寻找一个序列的最长递增子序列。 D. 使用Prim算法寻找图的最小生成树。
动态规划能够高效解决问题的关键在于利用了问题的什么性质？ A. 贪心选择性质和最优子结构。 B. 随机化和分治。 C. 最优子结构和重叠子问题。 D. 线性规划和对偶性。
对于0/1背包问题的空间优化解法（使用一维DP数组），其对背包容量的循环必须采用什么顺序？ A. 从小到大（正序）。 B. 从大到小（逆序）。 C. 任意顺序均可。 D. 取决于物品的输入顺序。
对于状态转移方程 $dp[i][j] = dp[i-1][j-1] + 1$ (当 s1[i] == s2[j])，它最可能是在解决什么问题？ A. 矩阵链乘。 B. 最长公共子序列。 C. 0/1背包。 D. 石子合并。
一个问题的最优解包含其子问题的最优解，这个性质被称为？ A. 贪心性质 B. 无后效性 C. 最优子结构 D. 重叠子问题

答案与解析:

C. (A)通常用BFS，(B)是分治，(D)是贪心算法。只有(C)是经典的DP问题。
C. 这是动态规划的两个基本要素。
B. 逆序遍历是为了保证每个物品只被考虑一次，避免状态更新的污染。
B. 这是最长公共子序列（LCS）在两个字符串字符匹配时的转移方程的一部分。
C. 这是最优子结构的定义。

第二部分：判断题

记忆化搜索（自顶向下DP）和递推（自底向上DP）在解决同一个问题时，时间复杂度总是相同的。 (✓) 解析：理论上，两者访问和计算的状态数量是相同的，所以时间复杂度在数量级上一致。但递推通常有更小的常数因子。
贪心算法做的每一步决策都是局部最优的，因此它一定能得到全局最优解。 (✗) 解析：这是贪心算法和动态规划的主要区别之一。贪心算法不一定能得到全局最优解，例如0/1背包问题。
在最长递增子序列（LIS）问题中， $dp[i]$ 表示前 $i$ 个元素的最长递增子序列的长度。 (✗) 解析：这是一个常见的错误理解。正确的定义是 “以第 $i$ 个元素结尾的” LIS长度，这样才能保证状态的可转移性。
区间DP的循环设计通常是先枚举区间长度，再枚举区间端点。 (✓) 解析：从小到大的区间长度保证了在计算大区间时，其依赖的子区间已经被计算完毕。

第三部分：程序阅读与补全

问题1：阅读程序

下列C++代码片段解决的是什么问题？

#include<bits/stdc++.h>
using namespace std;

int solve(string s1, string s2) {
    int n = s1.length(), m = s2.length();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (s1[i - 1] == s2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[n][m];
}

回答: 该代码解决的是最长公共子序列 (LCS) 问题。

问题2：程序补全

以下是计算字符串编辑距离（将字符串 s1 转换成 s2 所需的最少操作次数：插入、删除、替换）的代码。请补全状态转移的核心逻辑。

#include<bits/stdc++.h>
using namespace std;

int minDistance(string s1, string s2) {
    int n = s1.length(), m = s2.length();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
    for (int i = 0; i <= n; ++i) dp[i][0] = i;
    for (int j = 0; j <= m; ++j) dp[0][j] = j;

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (s1[i - 1] == s2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                // ****** 在下方补全代码 ******
                dp[i][j] = ____________________________________________;
                // **************************
            }
        }
    }
    return dp[n][m];
}

补全答案: dp[i][j] = min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]}) + 1; 或者分开写： dp[i][j] = 1 + min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1]));

解析: 当 s1[i-1] != s2[j-1] 时，有三种选择：

替换: 将 s1[i-1] 替换成 s2[j-1]。操作数 = 1 + s1[0..i-2] 到 s2[0..j-2] 的距离，即 1 + dp[i-1][j-1]。
删除: 删除 s1[i-1]。操作数 = 1 + s1[0..i-2] 到 s2[0..j-1] 的距离，即 1 + dp[i-1][j]。
插入: 在 s1 中插入 s2[j-1]。操作数 = 1 + s1[0..i-1] 到 s2[0..j-2] 的距离，即 1 + dp[i][j-1]。取这三者中的最小值。

【CSP-J初赛】动态规划（一）