动态规划入门：从零开始理解 DP

565 字

3 分钟

动态规划入门：从零开始理解 DP

2026-03-18

teaching

信息学竞赛

/

算法

/

动态规划

/

C++

什么是动态规划？#

动态规划（Dynamic Programming，简称 DP）是一种通过把原问题分解为相对简单的子问题来求解复杂问题的方法。

核心思想#

最优子结构：问题的最优解包含子问题的最优解
重叠子问题：不同的子问题有相同的子子问题
状态转移：从已知状态推导未知状态

经典例题：爬楼梯#

你需要爬 $n$ 阶楼梯，每次可以爬 1 阶或 2 阶。问有多少种不同的方法？

分析#

设 $f(n)$ 表示爬到第 $n$ 阶的方法数：

f(n) = \begin{cases} 1 & n = 1 \\ 2 & n = 2 \\ f(n-1) + f(n-2) & n > 2 \end{cases}

C++ 实现#

1
#include <iostream>
2
using namespace std;
3

4
int main() {
5
    int n;
6
    cin >> n;
7

8
    // dp[i] 表示爬到第 i 阶的方法数
9
    int dp[n + 1];
10
    dp[1] = 1;
11
    dp[2] = 2;
12

13
    for (int i = 3; i <= n; i++) {
14
        dp[i] = dp[i - 1] + dp[i - 2];
15
    }
16

17
    cout << dp[n] << endl;
18
    return 0;
19
}

经典例题：01 背包问题#

有 $n$ 个物品，第 $i$ 个物品重量为 $w_i$ ，价值为 $v_i$ 。背包容量为 $W$ 。求在不超过背包容量的前提下，能获得的最大价值。

状态定义#

$dp[i][j]$ 表示考虑前 $i$ 个物品、背包容量为 $j$ 时的最大价值。

状态转移方程#

dp[i][j] = \max(dp[i-1][j], \; dp[i-1][j-w_i] + v_i)

C++ 实现#

1
#include <iostream>
2
#include <algorithm>
3
using namespace std;
4

5
const int MAXN = 1005;
6
int dp[MAXN];
7
int w[MAXN], v[MAXN];
8

9
int main() {
10
    int n, W;
11
    cin >> n >> W;
12

13
    for (int i = 1; i <= n; i++) {
14
        cin >> w[i] >> v[i];
15
    }
16

17
    // 一维优化
18
    for (int i = 1; i <= n; i++) {
19
        for (int j = W; j >= w[i]; j--) {
20
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
21
        }
22
    }
23

24
    cout << dp[W] << endl;
25
    return 0;
26
}

NOTE
注意一维优化时，内层循环需要倒序遍历，以保证每个物品只被选一次。

练习题#

洛谷 P1048 采药 - 01 背包模板
洛谷 P1616 疯狂的采药 - 完全背包
洛谷 P1049 装箱问题 - 01 背包变形

总结#

问题类型	状态定义	转移方程	时间复杂度
爬楼梯	$f(n)$ ：方法数	$f(n) = f(n-1) + f(n-2)$	$O(n)$
01 背包	$dp[i][j]$ ：前 $i$ 件、容量 $j$ 的最大价值	$dp[i][j] = \max(dp[i-1][j], dp[i-1][j-w_i]+v_i)$	$O(nW)$