11-动态规划入门：从“状态”思考¶

目标¶

理解动态规划要解决什么问题：重复子问题 + 最优子结构
学会 DP 的三步：定义状态、写转移、设边界
能写 2~3 个入门 DP：爬楼梯、最小路径和、0/1 背包（入门版）
知道如何做空间优化（可选加分）

先决知识¶

理解复杂度与循环（见 09 章）
理解递归的“重复计算”问题（见 10 章 1）

1. DP 的直觉：把算过的结果记下来¶

专业名称：动态规划（Dynamic Programming，DP）
类比：做题时写草稿：同一个小结论算过一次就记下来，下次直接抄
作用：避免重复计算，把指数级的递归降到多项式级
规则/坑点：DP 不是“套公式”，关键在于状态定义是否合理

DP 三步（固定套路）：

定义状态：dp[i] 或 dp[i][j] 代表什么
写转移：怎么从已知状态推出新状态
设边界：最小规模怎么初始化

2. 例 1：爬楼梯（最经典入门）¶

题目：一次走 1 或 2 级台阶，走到第 n 级有多少种走法。

2.1 状态与转移¶

状态：dp[i] 表示走到第 i 级的方法数
转移：最后一步要么从 i-1 走 1 级来，要么从 i-2 走 2 级来
所以 dp[i] = dp[i-1] + dp[i-2]
边界：dp[0]=1（站在地面算 1 种），dp[1]=1

可运行代码：

#include <iostream>
#include <vector>

long long climbStairs(int n) {
    std::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];
    }
    return dp[n];
}

int main() {
    int n = 0;
    std::cin >> n;
    std::cout << "ways=" << climbStairs(n) << '\n';
    return 0;
}

2.2 空间优化（可选）¶

你会发现 dp[i] 只依赖前两个值，所以不需要整个数组。

#include <iostream>

long long climbStairs(int n) {
    if (n == 0) return 1;
    if (n == 1) return 1;
    long long a = 1;
    long long b = 1;
    for (int i = 2; i <= n; i++) {
        long long c = a + b;
        a = b;
        b = c;
    }
    return b;
}

int main() {
    int n = 0;
    std::cin >> n;
    std::cout << "ways=" << climbStairs(n) << '\n';
    return 0;
}

3. 例 2：最小路径和（二维 DP）¶

题目：给一个 n*m 的网格，每格有代价，从 (0,0) 走到 (n-1,m-1) 只能向右或向下，求最小代价和。

3.1 状态与转移¶

状态：dp[r][c] 表示走到 (r,c) 的最小代价
转移：只能从上面或左边来
dp[r][c] = min(dp[r-1][c], dp[r][c-1]) + cost[r][c]
边界：第一行只能从左来，第一列只能从上来

可运行代码（输入 n m，再输入 n*m 个整数）：

#include <iostream>
#include <vector>

int main() {
    int n = 0;
    int m = 0;
    std::cin >> n >> m;

    std::vector<std::vector<int>> cost(n, std::vector<int>(m, 0));
    for (int r = 0; r < n; r++) {
        for (int c = 0; c < m; c++) {
            std::cin >> cost[r][c];
        }
    }

    std::vector<std::vector<long long>> dp(n, std::vector<long long>(m, 0));
    dp[0][0] = cost[0][0];

    for (int c = 1; c < m; c++) {
        dp[0][c] = dp[0][c - 1] + cost[0][c];
    }
    for (int r = 1; r < n; r++) {
        dp[r][0] = dp[r - 1][0] + cost[r][0];
    }

    for (int r = 1; r < n; r++) {
        for (int c = 1; c < m; c++) {
            long long fromUp = dp[r - 1][c];
            long long fromLeft = dp[r][c - 1];
            dp[r][c] = (fromUp < fromLeft ? fromUp : fromLeft) + cost[r][c];
        }
    }

    std::cout << "minSum=" << dp[n - 1][m - 1] << '\n';
    return 0;
}

4. 例 3：0/1 背包（入门版）¶

题目：有 n 个物品，每个物品有重量 w 和价值 v，背包容量为 W，每个物品最多选一次，最大价值是多少。

4.1 状态与转移（先学一维 DP）¶

状态：dp[c] 表示容量为 c 时的最大价值
转移：对每个物品，倒序更新容量
dp[c] = max(dp[c], dp[c - w] + v)
边界：dp 全 0

可运行代码（输入 n W，接着 n 行 w v）：

#include <iostream>
#include <vector>

int main() {
    int n = 0;
    int W = 0;
    std::cin >> n >> W;

    std::vector<int> w(n), v(n);
    for (int i = 0; i < n; i++) {
        std::cin >> w[i] >> v[i];
    }

    std::vector<long long> dp(W + 1, 0);
    for (int i = 0; i < n; i++) {
        for (int c = W; c >= w[i]; c--) {
            long long cand = dp[c - w[i]] + v[i];
            if (cand > dp[c]) {
                dp[c] = cand;
            }
        }
    }

    std::cout << "best=" << dp[W] << '\n';
    return 0;
}

为什么要倒序？

如果正序，会导致同一个物品在一轮里被用多次（变成“完全背包”）
倒序保证每个物品只影响一次（0/1）

常见坑¶

错误：状态定义不清晰
结果：写不出转移，或写出来不对
正确：先用一句话定义 dp 的含义，再写转移
错误：忘记边界初始化
结果：第一行/第一列/起点不对
正确：把最小规模手算出来再写进代码
错误：0/1 背包用正序更新
结果：同一物品被重复使用
正确：容量倒序更新

小练习¶

练习 1：爬楼梯变种¶

题目：一次可以走 1、2、3 级台阶，求走到 n 的方法数
输入/输出：输入 n，输出 ways
约束：n <= 50
提示：dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
目标：练状态转移扩展

练习 2：最小路径和（带障碍）¶

题目：网格里某些格子不能走，求最小路径和或输出 -1
输入/输出：输出 minSum 或 -1
约束：障碍格子用 -1 表示
提示：dp 初始化时遇到障碍要特殊处理
目标：练边界处理

练习 3：背包输出最大价值¶

题目：实现 0/1 背包，输出最大价值
输入/输出：同本章例 3
约束：用一维 dp
提示：倒序更新容量
目标：把模板写熟

练习 4：解释题¶

题目：用一句话解释 DP 与递归的关系
输入/输出：无
约束：必须提到“记忆化/保存结果”
提示：从“重复子问题”入手
目标：把核心直觉讲清楚

小结¶

你现在应该掌握：

DP 三步：状态、转移、边界
一维/二维 DP 的基本写法
背包问题的倒序更新技巧

下一篇是综合项目：把前面学到的容器、函数、类、算法串起来，写一个可用的小程序。