再谈动态规划的正确打开方式：从记忆化搜索到动态规划

崔泽禹 · 2025-10-06 08:33:06 · 算法·理论

（也许是）动态规划的正确打开方式：从记忆化搜索到动态规划

动态规划（Dynamic Programming, DP）是算法设计中的一座高峰，它以其高效解决具有最优子结构和重叠子问题的复杂问题而著称。然而，许多初学者在理解和掌握动态规划时，直接从递推开始学起，过渡到动态规划时常常困惑于其状态的定义和维度的选择，比如说我自己。本文将提供一种更为自然且直观的视角：将动态规划视为记忆化搜索的自底向上的优化版本。理解了从搜索到记忆化再到动态规划的演变过程，更好地入门动态规划。

那么好，下面就开始动态规划的正确打开方式，面向动态规划的初学者或者想用记忆化搜索在 OI 赛制中想要拿到部分分的选手。

适用条件：最优子结构与重叠子问题

在正式开始讨论之前，我们必须重温动态规划适用的两大基本特征：

最优子结构：一个问题的最优解可以通过其子问题的最优解来构造。换句话说，原问题的解包含了子问题的最优解，且子问题之间相互独立。
- 例子：斐波那契数列，fib(n) = fib(n-1) + fib(n-2)，fib(n) 的最优解可以由 fib(n-1) 和 fib(n-2) 的最优解直接得到。
- 例子：01 背包问题，装前 i 件物品、容量为 j 的最优解可以由装前 i-1 件物品的子问题最优解推导。
- 反例：求最长严格递增路径的“路径方案数”，如果路径之间有依赖（如环），则最优子结构不成立。
重叠子问题：在求解问题的过程中，我们会反复遇到并求解相同的子问题。这正是动态规划能大幅提升效率的关键。
- 例子：斐波那契数列，fib(n-1) 和 fib(n-2) 在递归树中会被多次计算。
- 例子：完全背包、编辑距离等问题，很多子状态会被多次访问。
- 反例：归并排序，每个子区间只被处理一次，没有重叠子问题；分治法通常不具备重叠子问题。

这就说明，只有同时具备“最优子结构”和“重叠子问题”这两个特征的问题，才适合用动态规划来解决。如果一个问题的最优解无法由子问题的最优解直接构造（即不满足最优子结构），或者每个子问题只会被计算一次（即没有重叠子问题），那么动态规划就不适用，应该考虑其他算法（如贪心、分治等）。

这也被称为 “无后效性” 原则，即：当前状态的最优解只依赖于子问题的状态，而不依赖于求解子问题的具体过程或历史路径。也就是说，子问题的解一旦确定，就不会因为决策顺序或历史选择而改变。这一特性保证了我们可以安全地“记忆”每个子问题的解，并在需要时直接复用，从而实现高效的动态规划算法。

一、起点：朴素递归与记忆化搜索

我们首先从最自然、最直观的解题思路—— 递归 ——开始，一个具有最优子结构的问题，通常可以很容易地写出其递归求解函数。

1. 朴素递归：低效的根源

以斐波那契数列 题目为例：

fib(n) = \begin{cases} 1, & n = 1 \\ 1, & n = 2 \\ fib(n-1) + fib(n-2), & n \geq 3 \end{cases}

其朴素递归实现如下：

long long fib(int n) {
    if (n <= 2) {
        return 1;
    }
    // 存在大量的重复计算：例如 fib(5) 会计算 fib(3) 两次
    return fib(n - 1) + fib(n - 2);
}

这种实现的时间复杂度是指数级的 O(2^n)，因为它重复计算了大量的子问题。

2. 记忆化搜索：避免重复计算

为了消除重叠子问题带来的低效，我们引入记忆化方法。其核心思想是：

每当计算出一个子问题的解时，将其存储（通常在一个数组中），在下次需要这个子问题解时，直接查表而不是重新计算。

:::align{center} :::

这就是记忆化搜索，它是一种自顶向下的动态规划实现方式（补充说明：相同的颜色代表了 “重叠子问题”；每个节点的最优解依赖于其下方子节点的最优解，就代表了 “最优子结构”）。

::::info[自顶向下（Top-Down）]{open} 自顶向下是一种解决问题的方法论，指的是从问题的整体出发，递归地将大问题分解为更小的子问题，直到子问题足够简单可以直接求解。在动态规划中，记忆化搜索就是典型的自顶向下做法：我们从原问题出发，每次递归地解决子问题，并用一个存储结构（如数组或哈希表）记录已经计算过的子问题结果，避免重复计算。这样既保留了递归的直观性，又提升了效率。 ::::

以斐波那契数列为例，要求 fib(n)，我们会递归地调用 fib(n-1) 和 fib(n-2)，再进一步递归下去，直到 n=1 或 n=2 为止。整个过程就是从顶层问题逐步向下分解为更小的子问题，这就是自顶向下的思想。

使用纯数组作为记忆化数组，假设 n 的范围已知且不大：

long long memo[N];

long long fib(int n) {
    if (n <= 2) {
        return 1;
    }
    // 查表：如果已经计算过，直接返回
    if (memo[n] != -1) {
        return memo[n];
    }
    // 计算并存表
    memo[n] = fib(n - 1) + fib(n - 2);
    return memo[n];
}
// 在主函数或使用前初始化 
std::memset(memo, -1, sizeof(memo)); // -1 表示未计算，0 可能是有效值

当数据过大时，可用 map / unordered_map 实现：

std::map<int, long long> memo;

long long fib(int n) {
    if (n <= 2) {
        return 1;
    }
    if (memo.count(n)) {
        return memo[n];
    }
    memo[n] = fib(n - 1) + fib(n - 2);
    return memo[n];
}

记忆化搜索将时间复杂度降为 O(n)，因为每个子问题恰好只被计算一次。

这里通过 P7961 [NOIP2021] 数列说明如何实现将无返回值的朴素递归搜索（通过 3 个测试点）改为有返回值的记忆化搜索（通过 10 个测试点），从而拿到部分分，其朴素搜索的核心代码如下：

void dfs(int s, long long sum, long long res) {
    if (s == n + 1) {
        cnt = 0;
        tmp = sum;
        while (tmp) {
            cnt += (tmp & 1);
            tmp >>= 1;
        }
        if (cnt <= k) {
            ans += res;
            ans %= mod;
        }
        return;
    }
    for (int i = 0; i <= m; i++) {
        dfs(s + 1, sum + (1 << i), res * v[i] % mod);
    }
}

改为记忆化搜索步骤可概括为：

分析递归参数：确定哪些参数唯一标识一个子问题（如 s 和 sum），这些参数将作为记忆化数组的下标，移除存储递归答案的参数（如 res）；
设计记忆化结构：根据参数范围选择合适的数据结构（如数组 f[s][sum] 或哈希表）；
添加返回值：将 void 类型递归函数改为有返回值（如 long long），返回当前状态的方案数或最优解；
加记忆化判断：在递归入口处判断当前状态是否已计算过，若已计算则直接返回记忆化结果；
递归返回并存储结果：递归计算所有分支，将结果累加 / 取最优，并存入记忆化数组，最后返回；
初始化记忆化结构：在主函数或递归前初始化记忆化数组（如 memset(f, -1, sizeof(f));）。

其修改后的记忆化搜索代码如下：

long long dfs(int s, long long sum) {
    if (f[s][sum] != -1) {
        return f[s][sum]; 
    }
    if (s == n + 1) {
        cnt = 0;
        tmp = sum;
        while (tmp) {
            cnt += (tmp & 1);
            tmp >>= 1;
        }
        return cnt <= k;
    }
    long long res = 0;
    for (int i = 0; i <= m; i++) {
        res += dfs(s + 1, sum + (1 << i)) * v[i] % mod;
        res %= mod;
    }
    return f[s][sum] = res;
}

memset(f, -1, sizeof(f));

记忆化搜索练习题（使用记忆化搜索就可以 AC 的）：

P1434 [SHOI2002] 滑雪
P1544 三倍经验
P1535 [USACO08MAR] Cow Travelling S
P8658 [蓝桥杯 2017 国 A] 填字母游戏
P4017 最大食物链计数

二、关键过渡：理解记忆化搜索是一种 “只递不归” 的递归

这里先直接给出斐波那契数列的递推实现：

long long dp[N];

long long fib(int n) {
    dp[1] = 1; dp[2] = 1;
    for (int i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

不难发现：这个递推式正是搜索中的递归调用关系的“平移”——也就是说，递归函数如何通过参数调用自身，动态规划就如何通过状态转移方程迭代计算每个状态。还是以斐波那契数列为例，递归和递推分别写作：

fib(i) = fib(i-1) + fib(i-2) \quad i \geq 3

dp[i] = dp[i-1] + dp[i-2] \quad i \geq 3

本质上，递归的参数就是 DP 的下标，递归的返回值就是 DP 的状态值，递归的调用就是 DP 的状态转移（下节详细说明对应关系）。这样，记忆化搜索和动态规划在逻辑上实现了无缝衔接。

原因在于：记忆化搜索是一种 “只递不归” 的递归，这种递归可以转化为递推（动态规划）。所谓“只递不归”，意思是递归过程中我们只向下递进（递），每个子问题只会被计算一次，并且一旦计算完成就直接返回结果（通过查表），不会重复进入同一个子问题的递归分支，也不会在递归树中反复回溯（归）。这样，递归的本质就变成了一个有向无环图（DAG）的遍历，每个节点（子问题）只访问一次，最终可以用迭代的方式（即自底向上的动态规划）来实现同样的效果。

::::info[自底向上（Bottom-Up）]{open} 自底向上是一种系统化的求解方法，指的是从最简单、最小的子问题（通常是递归的终止条件）出发，逐步“迭代”地构建更大规模的子问题的解，直到最终解决原问题。在动态规划中，这意味着我们先填好所有基准状态，然后按照依赖关系有序地填充整个 DP 表。这样做的好处是消除了递归带来的函数调用开销，并且便于进行空间优化。自底向上的 DP 实现，正是记忆化搜索的“迭代版”。 ::::

记忆化搜索是通往标准的自底向上动态规划的桥梁。在这个过程中，最关键的洞察在于：

搜索函数中的参数，就是定义“子问题”的唯一标识，它们自然地构成了动态规划的“状态”维度。

下面详细说明记忆化搜索与动态规划两者之间的对应关系。

三、对应关系：从记忆化搜索到动态规划

1. 递归参数与 DP 状态维度的对应

以 01 背包问题 P1048 [NOIP 2005 普及组] 采药为例（本节最后附完整代码）。有 N 件物品和一个容量为 V 的背包。放入第 i 件物品耗费的费用是 c_i，得到的价值是 w_i。求解将哪些物品装入背包可使价值总和最大。递归搜索的函数可以设计为：

\text{dfs}(i, j)

其中：

参数 i：当前考虑下标从 1 开始的前 i 个物品（只从前 i 个物品中选择）。
参数 j：当前背包剩余容量为 j。

int dfs(int i, int j) {
    if (i == 0) return 0; // 没有物品可选
    if (memo[i][j] != -1) return memo[i][j]; // 直接返回以计算过的结果
    int res = dfs(i - 1, j); // 不选第 i 个物品
    if (j >= c[i]) {
        res = max(res, dfs(i - 1, j - c[i]) + w[i]); // 选第 i 个物品
    }
    return memo[i][j] = res;
}

memset(memo, -1, sizeof(memo));

这里的两个参数 i 和 j，就直接对应了动态规划数组的两个维度：

\text{dp}[i][j]

其中：

维度 1：只考虑前 i 个物品；
维度 2：背包容量为 j 时能获得的最大价值。

2. 递归分支与 DP 状态转移方程的对应

记忆化搜索中的递归调用，直接对应了动态规划中的状态转移方程。在背包问题中，从 dp[i][j] 的计算，依赖于 dp[i-1][\ldots]，这也是递归中调用子问题的过程。类比记忆化搜索，动态规划的状态转移方程实现如下：

dfs(i,j)=\max{(dfs(i-1,j),dfs(i-1,j-c[i])+w[i])} \quad j \geq c[i]

dp[i][j]=\max{(dp[i-1][j],dp[i-1][j-c[i]]+w[i])} \quad j \geq c[i]

for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= m; j++) {
        dp[i][j] = dp[i - 1][j]; // 不选第 i 件物品
        if (j >= c[i]) { // 选第 i 件物品
            dp[i][j] = max(dp[i][j], dp[i - 1][j - c[i]] + w[i]);
        }
    }
}

这正是记忆化搜索递归调用的“平移”版本，递归中的 “分支” 在动态规划中变成了取最大值的 “状态转移”。

这里再用两个经典问题简单说明这种对应关系。比如，对于最长上升子序列问题：

dfs(i)=\max{(dfs(j))}+1 \quad j<i\ 且\ num[j]<num[i]

dp[i]=\max{(dp[j])}+1 \quad j<i\ 且\ num[j]<num[i]

对于编辑距离问题：

dfs(i, j) = \begin{cases} dfs(i-1, j-1), & s_i = t_j \\ \min{(dfs(i-1, j),dfs(i, j-1),dfs(i-1, j-1))}+1, & s_i \neq t_j \end{cases}

dp[i][j] = \begin{cases} dp[i-1][j-1], & s_i = t_j \\ \min{(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])}+1, & s_i \neq t_j \end{cases}

我们可以看到，递归中的每一次分支调用，在动态规划中都被“平移”为状态转移方程的一项。这样，记忆化搜索的递归结构和动态规划的迭代结构在本质上是一一对应的。通过这种方式，我们能够系统地将递归解法转化为动态规划解法，实现从“自顶向下”到“自底向上”的平滑过渡。

3. 递归终止条件与 DP 初始值的对应

递归中的终止条件对应于动态规划的初始值，递归的终止条件是 i=0 时返回 0，即没有物品可选时最大价值为 0。在动态规划实现中，这对应于：

通常在代码实现时，初始化整个 dp 数组为 0 即可。有些问题要提别考虑边界初始值，初始值的设定直接影响动态规划的正确性。比如在最长上升子序列问题中，初始时应将所有 dp[i] 初始化为 1，表示每个元素自身可以构成长度为 1 的上升子序列。

4. 递归返回值与 DP 最终答案的对应

在记忆化搜索中，递归入口参数就是原问题的规模，返回值即为答案：

cout << dfs(n, m) << endl;

对应动态规划的最终答案，通常就是原问题对应的状态，dp[n][m] 表示考虑前 n 件物品、容量为 m 时的最大价值，因此 dp[n][m] 就是所求。

cout << dp[n][m] << endl;

有时，我们也需要遍历找到答案，比如在最长上升子序列问题中，dp[i] 表示以第 i 个元素结尾的最长上升子序列长度，最终答案应为所有 dp[i] 的最大值，即：

int ans = 0;
for (int i = 1; i <= n; i++) {
    ans = max(ans, dp[i]);
}
cout << ans << endl;

答案要根据题目、转移方程等因素来明确。比如在某些路径计数或方案数问题中，可能需要遍历所有可能的终点状态，取最大值、最小值或累加和作为最终答案。

这些便是记忆化搜索和动态规划之间的对应关系，总结如下：

::cute-table{tuack}

递归 / 记忆化搜索	动态规划
递归函数的参数	动态规划数组的维度
标识一个子问题的唯一状态	存储一个状态（子问题）的解
\text{dfs}(\mathbf{p}_1, \mathbf{p}_2, \ldots)	\text{dp}[\mathbf{p}_1][\mathbf{p}_2][\ldots]
递归终止条件	动态规划初始值
递归到边界时直接返回	初始化动态规划边界状态
递归分支 / 调用	状态转移方程
递归地调用子问题	由已知状态推导新状态
递归返回值	动态规划最终答案
递归入口的返回值即为答案	动态规划数组的目标状态即为答案
记忆化搜索特点	动态规划特点
递归实现，易于理解但可能爆栈	迭代实现，节省栈空间
便于处理复杂边界和剪枝	便于空间优化和整体遍历
代码结构灵活，适合少量状态	代码结构规范，适合大规模状态
自顶向下	自底向上

:::align{center} :::

其实，通过记忆化搜索也间接解释了为什么只有满足 “无后效性” 原则的问题才能使用动态规划来解决：

记忆化搜索的核心在于：每个子问题的解一旦被计算并存储下来，后续无论以何种方式再次遇到该子问题，都可以直接复用之前的结果，而不必关心其在递归树中的具体路径或历史决策。
如果一个问题不满足“无后效性”，即：当前状态的最优解会受到历史路径或决策顺序的影响，那么同样的参数组合下，子问题的解可能并不唯一，这样记忆化表就无法正确复用结果，动态规划也就失去了意义。

因此，只有当问题满足 “无后效性”，即子问题的解只依赖于当前状态，而与历史无关时，记忆化搜索和动态规划才能正确高效地工作。

:::success[01 背包：记忆化搜索代码]

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

const int N = 1005;

int n, m; // 物品数量和背包容量
int c[N], w[N]; // 物品重量和价值
int memo[N][N]; // 记忆化数组

int dfs(int i, int j) {
    if (i == 0) return 0; // 没有物品可选
    if (memo[i][j] != -1) return memo[i][j];
    int res = dfs(i - 1, j); // 不选第 i 个物品
    if (j >= c[i]) {
        res = max(res, dfs(i - 1, j - c[i]) + w[i]); // 选第 i 个物品
    }
    return memo[i][j] = res;
}

int main() {
    cin >> n >> m; // 在 P1048 中要调换 n 和 m 的输入顺序
    for (int i = 1; i <= n; i++) {
        cin >> c[i] >> w[i];
    }

    memset(memo, -1, sizeof(memo)); // 使用前初始化
    cout << dfs(n, m) << endl;

    return 0;
}

时间复杂度 O(n \cdot m)，空间复杂度 O(n \cdot m)。

:::

:::success[01 背包：动态规划代码（二维数组）]

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

const int N = 1005;

int n, m; // 物品数量和背包容量
int c[N], w[N]; // 物品重量和价值
int dp[N][N]; // 表示前 i 件物品，容量为 j 的背包所能获得的最大价值

int main() {
    cin >> n >> m; // 在 P1048 中要调换 n 和 m 的输入顺序
    for (int i = 1; i <= n; i++) {
        cin >> c[i] >> w[i];
    }

    memset(dp, 0, sizeof(dp)); // 初始值设定，本题中可省略
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            dp[i][j] = dp[i - 1][j]; // 不选第 i 件物品
            if (j >= c[i]) { // 选第 i 件物品
                dp[i][j] = max(dp[i][j], dp[i - 1][j - c[i]] + w[i]);
            }
        }
    }
    cout << dp[n][m] << endl; // 依据 dp 数组的定义，答案即为 dp[n][m]

    return 0;
}

时间复杂度 O(n \cdot m)，空间复杂度 O(n \cdot m)。

:::

四、动态规划：系统化的自底向上

铺垫了这么多，我们现在可以正式引入动态规划中的一些基本概念：

阶段：把所给问题的求解过程恰当地分成若干个相互联系的阶段，以便于求解。过程不同，阶段数就可能不同。描述阶段的变量称为阶段变量，常用 k 表示。阶段的划分，一般是根据时间和空间的自然特征来划分，但要便于把问题的过程转化为多阶段决策的过程。（在记忆化搜索中，阶段通常由递归参数中的某一项体现，例如递归到第 k 层）
状态：状态表示每个阶段开始面临的自然状况或客观条件，它不以人们的主观意志为转移，也称为不可控因素。通常一个阶段有若干个状态，状态通常可以用一个或一组数来描述，称为状态变量。（在记忆化搜索中，状态由递归函数的参数唯一确定）
决策：表示当过程处于某一阶段的某个状态时，可以做出不同的决定，从而确定下一阶段的状态，这种决定称为决策。不同的决策对应着不同的数值，描述决策的变量称决策变量。（在记忆化搜索中，决策体现在递归分支的不同选择）
状态转移方程：动态规划中本阶段的状态往往是上一阶段的状态和上一阶段的决策的结果，由第 i-1 段的状态 f(i-1) 和决策 u(i-1) 来确定第 i 段的状态，状态转移表示为 F(i)=T(f(i-1),u(i-1))；或是由第 i 段来确定第 i+1 段的状态，状态转移表示为 F(i+1)=T(f(i),u(i))，称为状态转移方程。（在记忆化搜索中，状态转移由递归调用关系体现）
策略：各个阶段决策确定后，整个问题的决策序列就构成了一个策略，对每个实际问题，可供选择的策略有一定范围，称为允许策略集合。允许策略集合中达到最优效果的策略称为最优策略。（在记忆化搜索中，策略对应于递归路径上所有决策的组合）

动态规划的标准形式，通常是自底向上的，即通过迭代而非递归来填充状态数组。这正是前文所述 “阶段→状态→决策→转移” 思想的具体实现：我们将问题划分为若干阶段，每个阶段用状态变量唯一描述，针对每个状态枚举所有可能的决策，通过状态转移方程将已知的子问题解递推出更大规模的状态解。自底向上的做法从最小、最简单的子问题（递归的终止条件 / 动态规划的初始值）出发，按照依赖顺序迭代填充整个 DP 表，直到得到原问题的解。这样不仅避免了递归的函数调用开销，还便于空间优化和整体遍历，是实际应用中最常见、最高效的动态规划实现方式。

1. 自底向上与迭代

从记忆化搜索转为自底向上动态规划，意味着：

确定维度：根据搜索参数确定 DP 数组的维度。
确定遍历顺序：确定计算的顺序，确保在计算 dp[i][j] 时，所有其依赖的子状态（例如 dp[i-1][\ldots]）都已经计算完毕。
初始化：确定 DP 数组的基准情况，对应于递归的终止条件。
状态转移：将递归调用转化为迭代公式。

2. 空间优化：降维打击

自底向上动态规划的另一个优势是便于进行空间优化。如果一个状态 dp[i][\ldots] 的计算只依赖于 dp[i-1][\ldots]，那么可以使用滚动数组或将二维数组优化为一维（可能要改变遍历顺序），大幅减少内存占用。这在空间要求严格的竞赛编程中尤其重要。

例如，在 01 背包问题中，我们可以使用滚动数组或直接变为一维数组进行优化：

:::success[01 背包：动态规划代码（滚动数组）]

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

const int N = 1005;

int n, m;
int c[N], w[N];
int dp[2][N]; // 使用滚动数组

int main() {
    cin >> n >> m; // 在 P1048 中要调换 n 和 m 的输入顺序
    for (int i = 1; i <= n; i++) {
        cin >> c[i] >> w[i];
    }

    memset(dp, 0, sizeof(dp));
    bool flag = 0;
    for (int i = 1; i <= n; i++) {
        flag = 1 - flag; // 交替使用两行
        for (int j = 0; j <= m; j++) {
            dp[flag][j] = dp[1 - flag][j];
            if (j >= c[i]) {
                dp[flag][j] = max(dp[flag][j], dp[1 - flag][j - c[i]] + w[i]);
            }
        }
    }
    cout << dp[flag][m] << endl;

    return 0;
}

时间复杂度 O(n \cdot m)，空间复杂度 O(m)。

:::

:::success[01 背包：动态规划代码（滚动数组不同版本）]

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

const int N = 1005;

int n, m;
int c[N], w[N];
int dp[2][N]; // 使用滚动数组

int main() {
    cin >> n >> m; // 在 P1048 中要调换 n 和 m 的输入顺序
    for (int i = 1; i <= n; i++) {
        cin >> c[i] >> w[i];
    }

    memset(dp, 0, sizeof(dp));
    int pre = 0, cur = 1; // 用于滚动数组的索引
    for (int i = 1; i <= n; i++) {
        swap(pre, cur); // 交换 pre 和 cur 的值，以便使用滚动数组
        for (int j = 0; j <= m; j++) {
            dp[cur][j] = dp[pre][j];
            if (j >= c[i]) {
                dp[cur][j] = max(dp[cur][j], dp[pre][j - c[i]] + w[i]);
            }
        }
    }
    cout << dp[cur][m] << endl;

    return 0;
}

时间复杂度 O(n \cdot m)，空间复杂度 O(m)。

:::

:::success[01 背包：动态规划代码（滚动数组取余版本）]

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

const int N = 1005;

int n, m;
int c[N], w[N];
int dp[2][N]; // 使用滚动数组

int main() {
    cin >> n >> m; // 在 P1048 中要调换 n 和 m 的输入顺序
    for (int i = 1; i <= n; i++) {
        cin >> c[i] >> w[i];
    }

    memset(dp, 0, sizeof(dp));
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            dp[i % 2][j] = dp[(i - 1) % 2][j];
            if (j >= c[i]) {
                dp[i % 2][j] = max(dp[i % 2][j], dp[(i - 1) % 2][j - c[i]] + w[i]);
            }
        }
    }
    cout << dp[n % 2][m] << endl;

    return 0;
}

时间复杂度 O(n \cdot m)，空间复杂度 O(m)。

:::

一维数组中注意要逆序遍历容量，原因在于：如果正序遍历容量 j，则在更新 dp[j] 时，dp[j - c[i]] 可能已经被本轮的第 i 件物品更新过，导致同一物品被重复选择（变成完全背包）；而逆序遍历可以保证 dp[j - c[i]] 仍然是上一轮（第 i-1 件物品）得到的结果，未被更新，确保每件物品最多只选一次，符合 01 背包的约束。

:::success[01 背包：动态规划代码（一维数组）]

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

const int N = 1005;

int n, m;
int c[N], w[N];
int dp[N]; // 一维数组

int main() {
    cin >> n >> m; // 在 P1048 中要调换 n 和 m 的输入顺序
    for (int i = 1; i <= n; i++) {
        cin >> c[i] >> w[i];
    }

    memset(dp, 0, sizeof(dp));
    for (int i = 1; i <= n; i++) {
        for (int j = m; j >= c[i]; j--) { // 逆序遍历
            dp[j] = max(dp[j], dp[j - c[i]] + w[i]);
        }
    }
    cout << dp[m] << endl;

    return 0;
}

时间复杂度 O(n \cdot m)，空间复杂度 O(m)。

:::

背包问题为动态规划中的经典问题，详见背包九讲。

五、总结

动态规划的“正确打开方式”是将其视为一个方法论的演进：

\boxed{\text{朴素递归} \xrightarrow[\text{避免重复计算}]{\text{引入记忆化}} \text{记忆化搜索（自顶向下）} \xrightarrow[\text{迭代求解、考虑空间优化}]{\text{确定维度、设计转移方程}} \text{动态规划（自底向上）}}

关键的对应关系：搜索函数 \text{dfs} 的参数列表 \rightarrow 对应 \text{dp} 数组的维度 \rightarrow 状态的定义。

然后基于此关系：设计转移方程 \rightarrow 设定初始值 \rightarrow 迭代求解 \rightarrow 找到答案 \rightarrow 考虑空间优化的逻辑解决动态规划相关问题。

通过这种方式，我们强行理解状态定义，而是可以自然地从一个可工作的递归解法（即记忆化搜索）中，提取出动态规划所需的全部要素：状态（维度）和转移（递归关系），从而逐步实现对动态规划的真正掌握。

因为递推要求预先定义状态和转移，而递归允许按需定义状态和调用，这是初学者感到困难的根本原因。但要注意的是：这种思考方式主要适用于在 OI 赛制中通过记忆化搜索快速拿到部分分，或者作为理解和设计动态规划状态与转移方程的辅助步骤。在 ICPC 等赛制中需要高效、严谨的正解时，仍然需要最终转化为标准的动态规划实现，从动态规划的角度思考问题，以获得更好的复杂度。

扩展阅读：贝尔曼方程

贝尔曼方程（Bellman Equation）是动态规划理论的核心，广泛应用于最短路、最优控制、马尔可夫决策过程（MDP）、强化学习等领域。它本质上描述了最优子结构：一个状态的最优值等于其所有可达前驱状态的最优值加上转移代价的最优组合。

1. 在 MDP 中的贝尔曼方程

在 MDP 中，贝尔曼方程描述了状态价值 V(s) 的递归关系：

V(s) = \max_{a \in A(s)} \left\{ R(s, a) + \gamma \sum_{s'} P(s'|s, a) V(s') \right\}

其中：

其简化版本可写作：

f(P)= \underset{R\in \text{pre}(P)}{\max/\min}\bigl\{ f(R) + w_{R\to P} \bigr\}

其中：

“\max/\min” 表示根据问题类型取最大值或最小值（如最大价值、最短路径等）。

这个方程的含义是：状态 P 的最优值等于所有能转移到 P 的前驱状态 R 的最优值加上转移代价中的最优解。

2. 题目中的贝尔曼方程

以单源最短路为例，设 d[u] 表示从起点 s 到 u 的最短距离，则：

d[u] = \min_{v \to u} \left\{ d[v] + w_{v \to u} \right\}

这是贝尔曼方程的体现，也正是 Bellman-Ford 算法的核心转移。

又比如在前文提到的最长上升子序列问题中，设 dp[i] 表示以第 i 个元素结尾的最长上升子序列长度，等于所有满足 j < i 且 num[j] < num[i] 的 dp[j] + 1 的最大值：

dp[i] = \max_{j \to i} \left\{ dp[j] + 1 \right\}

其中 j \to i 表示所有可以转移到 i 的前驱状态 j（即 j < i 且 num[j] < num[i]）。我们枚举所有可能的前驱状态 j，取最优解，体现了贝尔曼方程的思想。

3. 动态规划与贝尔曼方程的关系

动态规划与贝尔曼方程的关系如下：

状态转移方程就是具体问题下的贝尔曼方程；
动态规划的本质是枚举所有决策，取最优值，这正是贝尔曼方程的思想。

无论是记忆化搜索还是自底向上的动态规划，本质上都是在求解某种“最优性原理”递推下的最优解。贝尔曼方程正是这种递推的数学表达。它强调：一个状态的最优解等于所有可达前驱状态的最优解加上转移代价的最优组合：

在记忆化搜索中，我们通过递归和查表，隐式地实现了贝尔曼方程的递推。
在动态规划中，我们通过显式的状态转移方程，迭代地实现了贝尔曼方程。

因此，贝尔曼方程是动态规划和记忆化搜索的理论基础。理解贝尔曼方程，有助于我们抽象和设计各种 DP 问题的状态转移方程，也有助于理解为何“无后效性”是动态规划成立的根本。

闲话

高一初次接触动态规划时，就是从阶段、状态、转移等等概念引入，并不怎么会设计转移方程，让我一头雾水。直到某天我在学习状压 DP 时看到了 P1433 吃奶酪的这篇题解，让我忽然意识到，深搜里面的的参数，正是 DP 数组中的维度。为了帮助初学者更好地学习动态规划，写下了这篇文章，更多学习资料可以参见最后的附录。

正如动态规划要满足无后效性一样：

\mathit{Future\ \ never\ \ has\ \ to\ \ do\ \ with\ \ past\ \ time,\ \ but\ \ present\ \ does.}

现在决定未来，未来与过去无关。

也许是写给正在准备 CSP / NOIP / ICPC / CCPC 等等比赛或考试的你我：

与其对过去感到种种遗憾，不如思考如何找到当下的最优解。

及时解决问题，选择本就是一种前行。希望这篇文章能够有所帮助，感谢阅读，祝好。

::::info[文章 GenAI 使用说明]{open} 本文使用 Google Gemini 辅助完善基础框架，已检查其内容的正确性。 ::::