📖 第 6.1 章 ⏱️ 约 65 分钟 🎯 中级

第 6.1 章：动态规划入门

📝 前置条件： 确保理解递归（第 2.3 章）、数组/向量（第 2.3–3.1 章）和基本循环模式（第 2.2 章）。DP 直接建立在递归概念之上。

动态规划（DP）常被描述为「带记忆的聪明递归」。让我们从最简单的例子——斐波那契数列——从零建立这种直觉。

💡 核心思路： DP 解决具有两个性质的问题：

  1. 重叠子问题 —— 相同的子计算出现多次
  2. 最优子结构 —— 大问题的最优解可以由小问题的最优解构建

两者同时成立时，DP 将指数时间转化为多项式时间。

6.1.1 朴素递归的问题

斐波那契数列：0, 1, 1, 2, 3, 5, 8, 13, 21, ...

定义： F(0) = 0，F(1) = 1，F(n) = F(n-1) + F(n-2)（n ≥ 2）。

图示：斐波那契递归树和记忆化

fib(5) 的递归树暴露了问题：fib(3) 被计算了两次（红色节点）。记忆化在第一次计算时缓存每个结果，将 2^N 次调用减少到仅 N 次唯一调用——这是动态规划背后的基本洞察。

Fibonacci Memoization

朴素递归实现：

int fib(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    return fib(n-1) + fib(n-2);  // 递归
}

这是正确的，但慢得可怕：

📄 这是正确的，但**慢得可怕**： 
fib(5)
├── fib(4)
│   ├── fib(3)
│   │   ├── fib(2)
│   │   │   ├── fib(1) = 1
│   │   │   └── fib(0) = 0
│   │   └── fib(1) = 1
│   └── fib(2)           ← 再次计算！
│       ├── fib(1) = 1
│       └── fib(0) = 0
└── fib(3)               ← 再次计算！
    ├── fib(2)            ← 再次计算！
    │   ├── fib(1) = 1
    │   └── fib(0) = 0
    └── fib(1) = 1

fib(3) 被计算了两次，fib(2) 三次。对 fib(50)，调用次数超过 10^10。这是指数时间：O(2^n)。

核心洞察：我们在一遍遍重复计算相同的子问题。DP 解决了这个问题。

6.1.2 记忆化（自顶向下 DP）

记忆化 = 递归 + 缓存。计算之前，检查是否已经计算过这个值。若是，返回缓存的结果；若否，计算它、缓存它、返回它。

📄 C++ 完整代码 
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100;
long long memo[MAXN];

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

int main() {
    fill(memo, memo + MAXN, -1LL);  // 将所有值初始化为 -1（「未计算」标记）
    cout << fib(50) << "\n";        // 12586269025
    return 0;
}

现在每个值被计算恰好一次。时间复杂度：O(N)。🎉

6.1.3 递推（自底向上 DP）

递推从头开始构建答案——先计算小子问题，用它们计算更大的问题。

📄 C++ 完整代码 
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n = 50;
    vector<long long> dp(n + 1);

    // 初始条件
    dp[0] = 0;
    dp[1] = 1;

    // 自底向上填表
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];  // 使用已计算的值
    }

    cout << dp[n] << "\n";  // 12586269025
    return 0;
}

甚至可以优化空间：由于每个斐波那契数只依赖前两个，只需 O(1) 空间：

long long a = 0, b = 1;
for (int i = 2; i <= n; i++) {
    long long c = a + b;
    a = b;
    b = c;
}
cout << b << "\n";

记忆化 vs 递推

对 fib(4) 两种方式对比：

Memoization vs Tabulation

💡 核心区别： 自顶向下按需计算（只算用到的子问题），自底向上全量填表（按顺序算所有子问题）。两者时间复杂度相同，但自底向上没有递归栈开销。

方面记忆化（自顶向下）递推（自底向上）
方式递归加缓存迭代填表
内存使用只有已计算的状态所有状态（包括未用到的）
实现通常更直观可能需要想清楚填充顺序
栈溢出风险有（深度递归）无
速度稍慢（函数调用开销）稍快
USACO 偏好适合理解和思考适合最终提交

🏆 USACO 技巧： 竞赛中自底向上递推略有优势，因为它避免了潜在的栈溢出（在 N = 10^5 的题目中很关键），通常也更快。但若难以看清递推关系，先用自顶向下——这是一种很好的思考方式。

6.1.4 DP 四步法

每道 DP 题都遵循相同的做法：

DP 四步法——从状态定义到空间优化：

DP 4-Step Recipe

  1. 定义状态： 什么信息能唯一描述一个子问题？
  2. 定义递推： dp[状态] 如何依赖更小的状态？
  3. 确定初始条件： 最简单子问题的答案是什么？
  4. 确定顺序： 以什么顺序填表？

应用到斐波那契：

  1. 状态： dp[i] = 第 i 个斐波那契数
  2. 递推： dp[i] = dp[i-1] + dp[i-2]
  3. 初始条件： dp[0] = 0，dp[1] = 1
  4. 顺序： i 从 2 到 n（每个依赖更小的 i）

6.1.5 硬币找零——经典 DP

题目： 有面额为 coins[] 的硬币，凑出金额 W 最少需要多少枚？每种面额可以无限次使用。

示例： coins = [1, 5, 6, 9]，W = 11

先试试贪心（每次选最大的 ≤ 剩余金额）：

  • 贪心：9 + 1 + 1 = 3 枚 ← 不是最优！
  • 最优：5 + 6 = 2 枚 ← DP 能找到

这就是为什么贪心在这里失败，需要 DP。

图示：硬币找零 DP 表

DP 表展示了 dp[i]（凑出金额 i 的最少硬币数）从左到右的填写过程。对硬币 {1,3,4}，注意 dp[3]=1（直接用硬币 3）和 dp[6]=2（用两个 3）。

Coin Change DP

DP 定义

对 coins = {1, 5, 6} 的状态转移：

Coin Change State Transitions

  • 状态： dp[w] = 凑出恰好金额 w 的最少硬币数
  • 递推： dp[w] = 1 + min(对所有 c ≤ w 的硬币 c：dp[w - c])（使用硬币 c，然后最优地解决剩余的 w-c）
  • 初始条件： dp[0] = 0（凑出金额 0 需要 0 枚）
  • 答案： dp[W]
  • 顺序： w 从 1 到 W

完整演示：coins = [1, 5, 6, 9]，W = 11

📄 查看代码：完整演示：coins = [1, 5, 6, 9]，W = 11 
dp[0] = 0 （初始条件）

dp[1]：用硬币 1：dp[0]+1=1          → dp[1] = 1
dp[2]：用硬币 1：dp[1]+1=2          → dp[2] = 2
...
dp[5]：用硬币 1：dp[4]+1=5
        用硬币 5：dp[0]+1=1          → dp[5] = 1  ← 用 5 分硬币！
dp[6]：用硬币 1：dp[5]+1=2
        用硬币 5：dp[1]+1=2
        用硬币 6：dp[0]+1=1          → dp[6] = 1  ← 用 6 分硬币！
...
dp[11]：用硬币 5：dp[6]+1=2
         用硬币 6：dp[5]+1=2          → dp[11] = 2  ← 5+6 或 6+5！

dp 表：[0, 1, 2, 3, 4, 1, 1, 2, 3, 1, 2, 2]

答案：dp[11] = 2（硬币 5 和 6）✓

📄 C++ 完整代码 
// 最少硬币找零 — O(N × W)
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, W;
    cin >> n >> W;

    vector<int> coins(n);
    for (int &c : coins) cin >> c;

    const int INF = 1e9;
    vector<int> dp(W + 1, INF);  // dp[w] = 凑出 w 的最少硬币数
    dp[0] = 0;                    // 初始条件

    for (int w = 1; w <= W; w++) {
        for (int c : coins) {
            if (c <= w && dp[w - c] != INF) {
                dp[w] = min(dp[w], dp[w - c] + 1);  // ← 关键行
            }
        }
    }

    if (dp[W] == INF) {
        cout << "Impossible\n";
    } else {
        cout << dp[W] << "\n";
    }

    return 0;
}

复杂度分析：

  • 时间： O(N × W) —— 对每个金额 w（1..W），尝试所有 N 种硬币
  • 空间： O(W) —— 只需 dp 数组

6.1.6 方法数——硬币找零变体

题目： 用给定硬币凑出金额 W 有多少种不同方法？

有序（排列——顺序重要）：[1,5] 和 [5,1] 是不同的

vector<long long> ways(W + 1, 0);
ways[0] = 1;  // 凑出 0：一种方法（不用硬币）

for (int w = 1; w <= W; w++) {
    for (int c : coins) {
        if (c <= w) {
            ways[w] += ways[w - c];  // ← 关键行
        }
    }
}

无序（组合——顺序不重要）：[1,5] 和 [5,1] 是同一种

vector<long long> ways(W + 1, 0);
ways[0] = 1;

for (int c : coins) {           // 外层循环：硬币（每种硬币只考虑一次）
    for (int w = c; w <= W; w++) {  // 内层循环：金额
        ways[w] += ways[w - c];
    }
}

💡 核心思路： 循环顺序决定了计数的是组合还是排列！硬币在外层循环时，每种硬币只被「引入」一次，忽略了顺序。金额在外层循环时，每个金额每次重新形成，允许所有排列。

⚠️ 第 6.1 章常见错误

  1. 最小化问题用 0 而非 INF 初始化 dp： dp[w] = 0 表示「0 枚硬币」，永远不会被改善。用 dp[w] = INF，只有 dp[0] = 0。
  2. 使用 dp[w-c] 前不检查 dp[w-c] != INF： INF + 1 会溢出！始终检查子问题是否可解。
  3. 背包变体的循环顺序错误： 无界背包（硬币无限），金额正向循环；0/1 背包（每个只用一次），金额反向循环。搞错这一点会给出静默的错误答案。
  4. 用 INT_MAX 作为 INF 然后加 1： INT_MAX + 1 溢出成负数。用 1e9 或 1e18 作为 INF。
  5. 忘记初始条件： dp[0] = 0 至关重要，没有它什么都设不好。

本章总结

📌 核心要点

概念要点何时使用
重叠子问题相同计算指数级重复递归树中有重复调用
记忆化（自顶向下）缓存递归结果；易于编写递归结构清晰时
递推（自底向上）迭代填表；无栈溢出最终竞赛提交；大 N
DP 状态唯一标识子问题的信息仔细定义——决定了一切
DP 递推dp[状态] 如何依赖更小状态「转移方程」
初始条件最简单子问题的已知答案通常 dp[0] = 某个平凡值

🧩 DP 四步法速查

步骤问题斐波那契示例
1. 定义状态"dp[i] 代表什么？"dp[i] = 第 i 个斐波那契数
2. 写递推"dp[i] 依赖哪些更小的状态？"dp[i] = dp[i-1] + dp[i-2]
3. 确定初始条件"最小子问题的答案是什么？"dp[0]=0，dp[1]=1
4. 确定填充顺序"i 从小到大？从大到小？"i 从 2 到 n

❓ 常见问题

Q1：怎么判断一道题是 DP 题？

A：两个信号：① 题目问「最优值」或「方法数」（不是「输出具体方案」）；② 存在重叠子问题（暴力递归中相同子问题被计算多次）。若贪心能被证明正确，通常不需要 DP；否则很可能是 DP。

Q2：应该用自顶向下还是自底向上？

A：学习时用自顶向下（更自然地表达递归思维）；竞赛提交用自底向上（更快，无栈溢出）。两者都正确。若能快速写出自底向上，直接用它。

Q3：什么是「最优子结构」（无后效性）？

A：DP 的核心前提条件——一旦 dp[i] 确定，后续计算不会「回来」修改它。换句话说，dp[i] 的值只依赖于「过去」（更小的状态），而不是「未来」。若违反这个性质，不能用 DP。

Q4：INF 应该设为多少？

A：int 类型用 1e9（= 10^9），long long 类型用 1e18（= 10^18）。不要用 INT_MAX，因为 INT_MAX + 1 溢出成负数。

🔗 与后续章节的联系

  • 第 6.2 章（经典 DP）：扩展到 LIS、背包、网格路径——都是本章四步 DP 法的应用
  • 第 6.3 章（进阶 DP）：进入状压 DP、区间 DP、树形 DP——更复杂的状态定义，但思路相同
  • 第 3.2 章（前缀和）：差分数组有时可以替代简单 DP，前缀和数组可以加速 DP 中的区间计算
  • 第 4.1 章（贪心）vs DP：贪心可解的问题是 DP 的特例（每步局部最优 = 全局最优）；贪心失败时需要 DP

练习题

题目 6.1.1 — 爬楼梯 🟢 简单 每次可以爬 1 或 2 级台阶，有多少种方法爬 N 级台阶？

提示 这就是斐波那契！ways[1]=1，ways[2]=2。或从 ways[0]=1, ways[1]=1 开始，then ways[n] = ways[n-1] + ways[n-2]。
✅ 完整题解

核心思路： ways[n] = 到达台阶 n 的方法数。你从台阶 n-1（1 步）或台阶 n-2（2 步）到达。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n; cin >> n;
    if (n == 1) { cout << 1; return 0; }
    vector<long long> dp(n + 1);
    dp[1] = 1; dp[2] = 2;
    for (int i = 3; i <= n; i++)
        dp[i] = dp[i-1] + dp[i-2];
    cout << dp[n] << "\n";
}

复杂度： O(N) 时间，O(N) 空间（可用两个变量降为 O(1)）。

题目 6.1.2 — 最少硬币找零 🟡 中等 给定硬币面额 [1, 3, 4] 和目标 6，找最少硬币数。（期望答案：2 枚——用 3+3）

✅ 完整题解 
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, W; cin >> n >> W;
    vector<int> coins(n);
    for (int& c : coins) cin >> c;
    const int INF = 1e9;
    vector<int> dp(W + 1, INF);
    dp[0] = 0;
    for (int w = 1; w <= W; w++) {
        for (int c : coins) {
            if (c <= w && dp[w - c] != INF)
                dp[w] = min(dp[w], dp[w - c] + 1);
        }
    }
    cout << (dp[W] == INF ? -1 : dp[W]) << "\n";
}

贪心选 4 → 4+1+1 = 3 枚；DP 找 3+3 = 2 枚。复杂度： O(N × W)。

题目 6.1.3 — 瓷砖铺设 🟡 中等 用 1×2 多米诺骨牌（水平或垂直放置）铺满 2×N 的棋盘，有多少种方法？

提示 递推与斐波那契相同！关键洞察：在第 N 列放一块竖排骨牌，递归到 n-1；在第 N-1 和 N 列放两块横排骨牌，递归到 n-2。
✅ 完整题解 
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1e9 + 7;
int main() {
    int n; cin >> n;
    if (n == 1) { cout << 1; return 0; }
    vector<long long> dp(n + 1);
    dp[1] = 1; dp[2] = 2;
    for (int i = 3; i <= n; i++)
        dp[i] = (dp[i-1] + dp[i-2]) % MOD;
    cout << dp[n] << "\n";
}

复杂度： O(N)。

题目 6.1.4 — 有限次使用的硬币找零 🔴 困难 与硬币找零相同，但每种硬币最多用一次（0/1 背包），找最少硬币数。

提示 0/1 背包变体，关键技巧：将 w 从 W 反向迭代到 coins[i]，防止重复使用同一枚硬币。
✅ 完整题解 
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, W; cin >> n >> W;
    vector<int> coins(n);
    for (int& c : coins) cin >> c;
    const int INF = 1e9;
    vector<int> dp(W + 1, INF);
    dp[0] = 0;
    for (int i = 0; i < n; i++) {
        // 反向顺序：防止硬币 i 被用超过一次
        for (int w = W; w >= coins[i]; w--) {
            if (dp[w - coins[i]] != INF)
                dp[w] = min(dp[w], dp[w - coins[i]] + 1);
        }
    }
    cout << (dp[W] == INF ? -1 : dp[W]) << "\n";
}

为什么反向？ 正向时可能用更新过的 dp[w] 来更新自身——等于把同一枚硬币用了两次。复杂度： O(N × W)。

题目 6.1.5 — USACO Bronze：干草堆叠放 🔴 困难 N 次操作「给位置 L 到 R 的所有位置加 1」，求每个位置的最终值。

提示 差分数组：`diff[L]++`，`diff[R+1]--`，然后取前缀和得到最终值。
✅ 完整题解 
#include <bits/stdc++.h>
using namespace std;
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int n, q; cin >> n >> q;
    vector<long long> diff(n + 2, 0);
    while (q--) {
        int l, r; cin >> l >> r;
        diff[l]++;
        diff[r + 1]--;
    }
    long long cur = 0;
    for (int i = 1; i <= n; i++) {
        cur += diff[i];
        cout << cur << " \n"[i == n];
    }
}

复杂度： O(N + Q)。

🏆 挑战题：有障碍的唯一路径 N×M 网格有「.」格子和「#」障碍，统计从 (1,1) 到 (N,M) 只向右或向下移动的路径数，答案对 10^9+7 取模。（N, M ≤ 1000）

✅ 完整题解 
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1e9 + 7;
int main() {
    int n, m; cin >> n >> m;
    vector<string> grid(n);
    for (auto& row : grid) cin >> row;
    vector<vector<long long>> dp(n, vector<long long>(m, 0));
    if (grid[0][0] == '.') dp[0][0] = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (grid[i][j] == '#') { dp[i][j] = 0; continue; }
            if (i > 0) dp[i][j] = (dp[i][j] + dp[i-1][j]) % MOD;
            if (j > 0) dp[i][j] = (dp[i][j] + dp[i][j-1]) % MOD;
        }
    }
    cout << dp[n-1][m-1] << "\n";
}

复杂度： O(N × M) 时间和空间。

图示：斐波那契递归树

Fibonacci Recursion Tree

上图展示了 fib(6) 的朴素递归。红色虚线节点是重复子问题——被多次计算。绿色节点展示记忆化缓存结果的位置。不用记忆化：O(2^N)；用记忆化：O(N)。这是动态规划背后的基本洞察。