第 6.1 章：动态规划入门

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

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

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

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

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

📚 本章学习地图

🧭 建议阅读方式： 初学者先完整读 §6.1.1–§6.1.4，确认能解释「为什么要缓存」和「表格怎么填」。如果你已经会基础 DP，可以直接跳到 §6.1.7–§6.1.8，重点训练从题面设计状态。

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 次唯一调用——这是动态规划背后的基本洞察。

朴素递归实现：

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）

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

#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）

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

#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;
}

手动追踪：dp 数组如何变化

只看代码时，初学者很容易知道“循环写对了”，但不知道数组到底怎么被填出来。以 n = 6 为例，dp 数组会这样变化：

这个表格就是递推代码的真实执行过程：每次循环只负责填一个新格子，并且只依赖已经填好的旧格子。

甚至可以优化空间：由于每个斐波那契数只依赖前两个，只需 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) 两种方式对比：

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

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

6.1.4 DP 四步法

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

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

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）

学 DP 时一定要补上的第 5 步：手动追踪

很多 DP 题看懂状态和转移后，真正卡住的地方并不是代码语法，而是：不知道循环执行时 dp 数组到底怎样一步步变化。

因此每学一道新 DP 题，都建议拿一个很小的样例，手动画出：

1. 初始数组是什么样。 哪些位置是 0，哪些位置是 INF 或“不可能”。
2. 外层循环每走一步，新增或更新了哪些状态。 例如填完 i = 3 后，dp[0..3] 分别是多少。
3. 某个格子为什么变成这个值。 它来自哪个旧状态？有没有和其他候选值取 min / max？
4. 最终答案从哪里取。 是 dp[n]，还是要在一组状态里再取最大值/最小值。

后面的例题会加入更多这样的“手动追踪表”，帮助你把递推式和代码执行过程对应起来。

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）。

DP 定义

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

• 状态： 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

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）✓

手动追踪：每一轮金额填完后的 dp 数组

下面这张表展示 coins = [1, 5, 6, 9]、W = 11 时，外层循环每处理完一个金额 w 后，dp[0..11] 的变化。∞ 表示当前还凑不出来。

注意 w = 5、w = 6、w = 9 这些位置会突然变小，因为它们可以直接使用面额为 5、6、9 的硬币。

// 最少硬币找零 — 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 有多少种不同方法？每种硬币可以使用无限次。

这一类题和“最少硬币数”很像，但目标变了：

• 最少硬币数：求 min。
• 方法数：求 sum。

先定义状态：ways[w] 表示什么？

ways[w] = 凑出金额 w 的方法数

最重要的初始条件是：

ways[0] = 1;

这句话一开始很反直觉：金额 0 为什么有 1 种方法？

因为它表示“什么都不选”这一种空方案。它的作用是给后面的转移提供起点。例如如果有一枚硬币 5，那么：

ways[5] += ways[5 - 5]
ways[5] += ways[0]

如果 ways[0] 不是 1，就无法正确产生“只用一枚 5 元硬币”这 1 种方法。

情况一：有序方法数（排列）

有序表示顺序重要：[1, 5] 和 [5, 1] 是两种不同方法。

这时我们按“最后一枚硬币是什么”来思考。

如果要凑出金额 w，最后一枚硬币可能是任意 c。那么前面的部分必须凑出 w - c：

ways[w] += ways[w - c]

代码如下：

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];
        }
    }
}

注意外层循环是金额 w。这代表：我们依次计算 ways[1]、ways[2]、ways[3]……每个 ways[w] 都会尝试把每种硬币放在最后。

手动追踪：有序方法数

以 coins = [1, 2]，W = 4 为例。

所以有序时，凑出 4 的 5 种方法是：

1 + 1 + 1 + 1
1 + 1 + 2
1 + 2 + 1
2 + 1 + 1
2 + 2

可以看到，1 + 1 + 2、1 + 2 + 1、2 + 1 + 1 被算作三种不同方法，因为顺序不同。

情况二：无序方法数（组合）

无序表示顺序不重要：[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];
    }
}

这段代码的含义是：

• 处理硬币 1 后，ways[w] 表示“只使用硬币 1”能凑出 w 的方法数。
• 再处理硬币 2 后，ways[w] 表示“只使用硬币 1 和 2”能凑出 w 的方法数。
• 如果还有硬币 5，处理完后，ways[w] 表示“只使用硬币 1、2、5”能凑出 w 的方法数。

因为硬币种类是按固定顺序引入的，所以同一组硬币不会因为排列顺序不同而被重复计算。

手动追踪：无序方法数

仍然看 coins = [1, 2]，W = 4。

所以无序时，凑出 4 的 3 种方法是：

1 + 1 + 1 + 1
1 + 1 + 2
2 + 2

这里不会再单独统计 1 + 2 + 1、2 + 1 + 1，因为它们和 1 + 1 + 2 使用的是同一组硬币。

为什么只是交换两层循环，答案就不同？

关键在于 ways[w] 在循环中代表的含义不同。

可以用一句话记住：

金额在外层，枚举的是“最后一步”，所以会统计顺序；硬币在外层，枚举的是“使用哪些硬币种类”，所以不会统计顺序。

用 [1, 5] 和 [5, 1] 理解重复统计

假设 coins = [1, 5]，要凑出 6。

有序写法中，计算 ways[6] 时：

• 最后一枚是 1：来自 ways[5]，其中包含 [5]，于是得到 [5, 1]。
• 最后一枚是 5：来自 ways[1]，其中包含 [1]，于是得到 [1, 5]。

所以 [1, 5] 和 [5, 1] 会被分开统计。

无序写法中，先处理硬币 1，再处理硬币 5。当处理硬币 5 时，只会把 5 加到“已经由硬币 1 组成的方法”后面，于是得到的是同一种组合 {1, 5}，不会再倒过来统计一次。

易错点提醒

1. 忘记 ways[0] = 1。 这样所有方法数都会变成 0，因为没有起点。
2. 把排列和组合的循环顺序写反。 如果题目说“顺序不同算不同方法”，金额放外层；如果题目说“硬币组合”，硬币放外层。
3. 方法数可能很大。 题目通常会要求对某个数取模，例如 1e9 + 7，这时每次加法后都要 % MOD。

6.1.7 状态设计四问：从题目到 DP 表

很多同学觉得 DP 难，不是因为代码难，而是因为不知道 dp[...] 到底该表示什么。遇到新题时，先不要急着写递推式，按下面四个问题拆开：

💡 状态设计口诀： dp 状态必须刚好包含「决定未来所需的信息」。少了会无法转移，多了会爆内存或超时。

6.1.8 USACO 真题训练：状态设计实战

真题 1：Hoof, Paper, Scissors（USACO 2017 January Gold）— 三维状态 DP

题目链接： USACO 2017 January Gold P2: Hoof, Paper, Scissors
对应模式： 序列 DP + 有限次状态切换
难度定位： Gold 入门

题干解读

Bessie 和 FJ 玩 N 轮 Hoof, Paper, Scissors。三种手势分别是 H（Hoof）、P（Paper）、S（Scissors），胜负关系为：H 赢 S，P 赢 H，S 赢 P。

FJ 接下来 N 轮会出的手势已经提前给出。Bessie 可以根据这份完整序列来安排自己每一轮的手势，但她最多只能改变手势 K 次。也就是说，Bessie 第 1 轮前选择初始手势不算改变；之后只有当第 i 轮和第 i-1 轮使用的手势不同时，才算改变 1 次。目标是让 Bessie 赢的轮数尽可能多。

例如，如果 K = 0，Bessie 只能整场都出同一种手势；如果 K = 1，她最多可以先连续出一种手势，再在某一轮之后切换成另一种手势。

关键条件：

• N 很大，不能枚举所有手势序列。
• K 较小，说明「换了几次」适合作为 DP 维度。
• 当前出什么手势会影响下一轮是否算「改变」，所以当前手势也必须记住。

思路分析

状态定义：

dp[i][j][g] = 处理前 i 轮，已经换了 j 次，当前手势为 g 的最多胜场

第 i 轮可以：

• 继续用手势 g：不增加切换次数。
• 从其他手势切换到 g：切换次数 +1。

每轮还要加上 g 是否能赢 FJ 第 i 轮手势的得分。

手动追踪：三维状态如何变化

三维数组不适合完整画出来，可以把 dp[i][used][g] 按 used 分层看。下面用一个小样例：

N = 4, K = 1
FJ = H S H P

表中 [H, P, S] 表示当前手势分别为 H/P/S 时的最多胜场，- 表示这个状态不可能出现。

读这张表时，可以抓住两个动作：

• 不换手势：例如 i = 3, used = 0, P 来自上一轮 used = 0, P，再加上 P 赢 H 的 1 分，所以从 1 变成 2。
• 换手势：例如 i = 4, used = 1, S 可以从上一轮 used = 0, P 切换而来。上一轮 P 的最好成绩是 2，这一轮 S 赢 P 再加 1 分，所以得到 3。

最终答案是所有 used <= K、所有当前手势中的最大值，也就是 3。

CPP 完整代码

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

int gestureId(char c) {
    if (c == 'H') return 0;
    if (c == 'P') return 1;
    return 2;  // 'S'
}

bool win(int bessie, int fj) {
    // H beats S, P beats H, S beats P
    return (bessie == 0 && fj == 2) ||
           (bessie == 1 && fj == 0) ||
           (bessie == 2 && fj == 1);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // USACO 官方文件 I/O 可按需打开：
    // freopen("hps.in", "r", stdin);
    // freopen("hps.out", "w", stdout);

    int n, k;
    cin >> n >> k;
    vector<int> fj(n + 1);
    for (int i = 1; i <= n; i++) {
        char c;
        cin >> c;
        fj[i] = gestureId(c);
    }

    const int NEG = -1e9;
    vector dp(n + 1, vector(k + 1, vector<int>(3, NEG)));

    // 第 1 轮可以直接选择任意手势，不算切换
    for (int g = 0; g < 3; g++) {
        dp[1][0][g] = win(g, fj[1]) ? 1 : 0;
    }

    for (int i = 2; i <= n; i++) {
        for (int used = 0; used <= k; used++) {
            for (int cur = 0; cur < 3; cur++) {
                int score = win(cur, fj[i]) ? 1 : 0;

                // 不换手势
                dp[i][used][cur] = max(dp[i][used][cur], dp[i - 1][used][cur] + score);

                // 从其他手势切换到 cur
                if (used > 0) {
                    for (int prev = 0; prev < 3; prev++) {
                        if (prev == cur) continue;
                        dp[i][used][cur] = max(dp[i][used][cur], dp[i - 1][used - 1][prev] + score);
                    }
                }
            }
        }
    }

    int answer = 0;
    for (int used = 0; used <= k; used++) {
        for (int g = 0; g < 3; g++) {
            answer = max(answer, dp[n][used][g]);
        }
    }

    cout << answer << "\n";
    return 0;
}

易错点提醒

1. 把「最多 K 次」写成「恰好 K 次」。 最后答案要枚举 used = 0..K。
2. 初始状态错误。 第 1 轮可以直接选择任意手势，不算切换，所以 dp[1][0][g] 应初始化为第 1 轮得分。
3. 胜负关系写反。 H/P/S 与石头剪刀布类似，但名字不同，建议写独立 win() 函数。
4. 状态缺少当前手势。 如果只写 dp[i][j]，无法判断下一轮是否发生切换。

拓展思考

如果手势种类从 3 种变成 M 种，复杂度会变为 O(NKM^2)。此时可以维护每个 used 层的最大值和次大值，将切换转移优化到 O(NKM)。

真题 2：Teamwork（USACO 2018 December Gold）— 枚举最后一组

题目链接： USACO 2018 December Gold P3: Teamwork
对应模式： 一维 DP + 枚举最后一段
难度定位： Gold 入门

题干解读

N 头奶牛排成一行，每头有技能值。可以把连续奶牛分成若干组，每组长度不超过 K。一组中所有奶牛的贡献都变成该组最大技能值。求最大总贡献。

关键条件：

• 分组必须是连续段。
• 每组长度最多 K。
• 每一段的贡献是 长度 × 段内最大值。

思路分析

从前往后考虑。设：

dp[i] = 前 i 头奶牛分组后的最大总贡献

最后一组可能长度为 len = 1..K，覆盖 [i-len+1, i]。只要枚举最后一组长度，就能把问题拆成：

dp[i] = max(dp[i-len] + len * max(skill[i-len+1..i]))

枚举 len 时同步维护当前段最大值，避免每次重新扫描。

手动追踪：dp[i] 如何一步步更新

用一个小样例观察代码执行过程：

N = 5, K = 3
skill = [1, 15, 7, 9, 2]

dp[i] 表示前 i 头奶牛已经分好组后的最大总贡献。每一行都在枚举“最后一组”的长度。

这张表对应代码里的内层循环：len 从 1 增加到 K，groupMax 一边向左扩展最后一组，一边维护这组里的最大技能值。

CPP 完整代码

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // USACO 官方文件 I/O 可按需打开：
    // freopen("teamwork.in", "r", stdin);
    // freopen("teamwork.out", "w", stdout);

    int n, k;
    cin >> n >> k;
    vector<int> skill(n + 1);
    for (int i = 1; i <= n; i++) cin >> skill[i];

    vector<int> dp(n + 1, 0);

    for (int i = 1; i <= n; i++) {
        int groupMax = 0;
        for (int len = 1; len <= k && i - len + 1 >= 1; len++) {
            groupMax = max(groupMax, skill[i - len + 1]);
            dp[i] = max(dp[i], dp[i - len] + groupMax * len);
        }
    }

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

易错点提醒

1. 最后一组左端点越界。 条件必须包含 i - len + 1 >= 1。
2. 每次重新求区间最大值。 会变成 O(NK^2)；应在枚举 len 时维护 groupMax。
3. 状态定义不清。 dp[i] 必须表示「前 i 头已经完全分好组」，这样 dp[i-len] 才能无缝接上最后一组。
4. 误以为是贪心。 每次把强奶牛尽量扩组不一定最优，因为会影响后面组的边界。

拓展思考

Teamwork 是「枚举最后一段」DP 的典型例子。类似模式还会出现在：分割数组、文本换行、区间分段最优化中。识别信号是：答案由若干连续段组成，每段有独立贡献，段长有限制。

⚠️ 第 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 至关重要，没有它什么都设不好。

本章总结

📌 核心要点

🧩 DP 四步法速查

❓ 常见问题

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 级台阶？

#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";
}

题目 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";
}

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

#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";
}

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

#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";
}

题目 6.1.5 — USACO Bronze：干草堆叠放 🔴 困难 N 次操作「给位置 L 到 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];
    }
}

🏆 挑战题：有障碍的唯一路径 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;
上图展示了 fib(6) 的朴素递归。红色虚线节点是**重复子问题**——被多次计算。绿色节点展示记忆化缓存结果的位置。不用记忆化：`O(2^N)`；用记忆化：`O(N)`。这是动态规划背后的基本洞察。