Tommy Chen home

动态规划

2 Nov 2025

1. 简介

动态规划（Dynamic Programming，DP）是一种把大问题拆成小问题、保存小问题答案，再逐步推出大问题答案的方法。

当一个问题的不同求解过程会反复遇到相同的小问题时，直接递归会重复计算。动态规划把这些结果记录在数组中，每个状态只计算一次，从而提高效率。

写动态规划时，通常需要先确定四件事：

状态表示什么。
当前状态如何由更小的状态转移而来。
最小状态的初始值是什么。
状态应按什么顺序计算。

2. 基本思路

最常见的状态形式是 dp[i]。它可以表示前 i 个元素的最优答案、到达位置 i 的方案数，或以位置 i 结尾的某种最优值。

找到状态含义后，观察“最后一步”或“最后一次选择”。如果到达当前状态的方式可以由几个更小的状态组成，就可以写出状态转移方程。计算时必须先得到转移所依赖的状态，因此通常按下标从小到大循环。

3. 例子：爬楼梯

有 n 级台阶，每次可以走 1 级或 2 级，问走到第 n 级一共有多少种方法。

定义 dp[i] 为走到第 i 级台阶的方法数。最后一步只有两种情况：

从第 i - 1 级走 1 步过来。
从第 i - 2 级走 2 步过来。

这两种情况不会重复，因此：

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

初始时，dp[0] = 1 表示“不走任何一步”也算一种方法；dp[1] = 1。之后按从小到大的顺序计算即可。

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

int main() {
    int n;
    cin >> n;

    vector<long long> dp(n + 1, 0);
    dp[0] = 1;
    if (n >= 1) dp[1] = 1;

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

    cout << dp[n];
    return 0;
}

例如 n 为 4 时，方法数为 5：1+1+1+1、1+1+2、1+2+1、2+1+1、2+2。

这个例子的时间复杂度是 O(n)，空间复杂度是 O(n)。由于 dp[i] 只依赖前两个状态，实际也可以只用两个变量，把空间复杂度优化为 O(1)。动态规划的重点不在于背公式，而是清楚地说明每一个状态代表什么，以及它为什么能从前面的状态推出。

动态规划

Related Posts