第 11 章十个算法思想 · C++ 新手进阶教材（11/13）

🧮 这一章正在拆分：十个算法思想会陆续整理成语言无关的数据结构与算法线，每个专题都给出 C / C++ / Java / Python 四语言完整可运行代码。目前第 1 章链表已经上线。

🎯 本章你会学到：双指针到动态规划，十种思想的模板与练习。建议边读边敲代码，每节的练习先自己做，再展开答案对照。

算法思想不是背代码，而是一套“看到题目 → 识别模式 → 套用模板”的思维。这十个思想是数据结构课和算法竞赛的公共词汇：查找与区间（双指针、滑动窗口、哈希表、前缀和、二分查找）、搜索与规划（DFS、BFS、回溯、贪心、DP）。每个思想给出：白话解释、模板、复杂度、适用场景和易错点，然后两道题练手。

11.1 双指针

思想：在有序数组里，两个指针分别从两端向中间走，利用单调性跳过大量无效枚举，把 O(n²) 降到 O(n)。

模板与适用场景

经典场景“两数之和（有序）”：left 指向头、right 指向尾，sum = a[left] + a[right]；sum < target 时 left++（总和太小，必须增大），sum > target 时 right--，相等则命中。每次只动一个指针，却排除了整行/整列的可能性——这就是双指针快的本质。

示例代码

int l = 0, r = (int)a.size() - 1;
while (l < r) {
    int sum = a[l] + a[r];
    if (sum == target) { /* 找到 */ break; }
    else if (sum < target) { ++l; }
    else { --r; }
}

⏱ 复杂度　时间复杂度 O(n)，空间 O(1)（需数组有序）

⚠️ 易错点　前提是有序（或具有单调性）。无序数组用双指针是错的——要先排序或换哈希表。另一变体：同向双指针（快慢指针）用于链表找中点、判环。

✍️ 本节练习

11.1.1必做两数之和（有序）

升序数组，找两个数使和等于 target，输出它们的下标（保证存在唯一一组解，下标从 0 开始）。

输入　第一行 n target；第二行 n 个升序整数。

输出　两个下标，空格分隔。

样例输入

5 8
1 2 3 5 6

样例输出

1 4

💡 提示　和太小 ++l，和太大 --r。

✅ 查看参考答案与解析

#include <iostream>
#include <vector>
int main() {
    int n, target;
    std::cin >> n >> target;
    std::vector<int> nums(n);
    for (int i = 0; i < n; ++i) { std::cin >> nums[i]; }
    int l = 0, r = n - 1;
    while (l < r) {
        int s = nums[l] + nums[r];
        if (s == target) { std::cout << l << ' ' << r << '\n'; return 0; }
        if (s < target) { ++l; } else { --r; }
    }
    return 0;
}

解析　双指针利用有序性：每步排除一个元素，O(n)。

11.1.2挑战回文判断

读入一个字符串（仅小写字母），用相向双指针判断它是否回文，是输出 yes，否则输出 no。

输入　一行字符串。

输出　yes 或 no。

样例输入

abcba

样例输出

yes

💡 提示　l 从 0、r 从末尾，比较 s[l] 和 s[r]，不等就 no。

✅ 查看参考答案与解析

#include <iostream>
#include <string>
int main() {
    std::string s;
    std::cin >> s;
    int l = 0, r = (int)s.size() - 1;
    while (l < r) {
        if (s[l] != s[r]) { std::cout << "no\n"; return 0; }
        ++l;
        --r;
    }
    std::cout << "yes\n";
    return 0;
}

解析　相向双指针：一对一对往中间比，O(n)。

11.2 滑动窗口

思想：维护一个窗口 [left, right)，右指针不断扩窗、左指针按需缩窗，让“连续子数组/子串”问题每次只改窗口两端，O(n) 内完成。

模板与适用场景

适用：求满足条件的连续子数组/子串的最长、最短、个数。窗口内用计数数组或 map 维护状态。扩展窗口（right++）时更新状态；违反条件时收缩（left++）直到重新满足；每次更新答案。核心技巧：right 只管进，left 只管出，用 while 让窗口重新合法。

示例代码

int left = 0, ans = 0;
std::map<char, int> cnt;
for (int right = 0; right < (int)s.size(); ++right) {
    ++cnt[s[right]];                              // 右端进窗
    while (cnt[s[right]] > 1) {                   // 违反条件：缩窗
        --cnt[s[left]]; ++left;
    }
    ans = std::max(ans, right - left + 1);        // 更新答案
}

⏱ 复杂度　时间复杂度 O(n)，空间 O(字符集大小)

⚠️ 易错点　注意窗口合法条件是什么（最长无重复 / 和 >= target）；缩窗时更新状态和移动 left 必须成对。

✍️ 本节练习

11.2.1必做最长无重复子串

给一个字符串，输出最长无重复字符子串的长度。

输入　一行字符串（小写字母，长度 ≤ 100000）。

输出　一个整数。

样例输入

abcabcbb

样例输出

💡 提示　cnt[26] 记录窗口内字符出现次数；出现重复就收缩左指针。

✅ 查看参考答案与解析

#include <iostream>
#include <string>
#include <vector>
int main() {
    std::string s;
    std::cin >> s;
    std::vector<int> cnt(26, 0);
    int l = 0, ans = 0;
    for (int r = 0; r < (int)s.size(); ++r) {
        ++cnt[s[r] - 'a'];
        while (cnt[s[r] - 'a'] > 1) {
            --cnt[s[l] - 'a'];
            ++l;
        }
        ans = std::max(ans, r - l + 1);
    }
    std::cout << ans << '\n';
    return 0;
}

解析　窗口内无重复时随时更新答案；有重复就收缩，O(n)。

11.2.2挑战和 ≥ target 最短子数组

给 n 个正整数和 target，输出和大于等于 target 的最短连续子数组长度；不存在输出 -1。

输入　第一行 n target；第二行 n 个正整数。

输出　最短长度或 -1。

样例输入

6 7
2 3 1 2 4 3

样例输出

💡 提示　先扩张右端让和达到 target，再收缩左端并更新最短长度——经典最小覆盖窗口。

✅ 查看参考答案与解析

#include <algorithm>
#include <iostream>
#include <vector>
int main() {
    int n, target;
    std::cin >> n >> target;
    std::vector<int> a(n);
    for (int i = 0; i < n; ++i) { std::cin >> a[i]; }
    int l = 0, sum = 0, ans = n + 1;
    for (int r = 0; r < n; ++r) {
        sum += a[r];
        while (sum >= target && l <= r) {
            ans = std::min(ans, r - l + 1);
            sum -= a[l];
            ++l;
        }
    }
    std::cout << (ans > n ? -1 : ans) << '\n';
    return 0;
}

解析　右端扩张到和够大，左端收缩找最短，每步窗口都“刚刚够”——这是最小覆盖窗口模板。

11.3 哈希表

思想：用 unordered_map/set 把“查找”从 O(n) 降到平均 O(1)。用空间换时间，是“两数之和”“计数统计”的第一反应。

模板与适用场景

适用：判断元素是否存在、统计频率、配对查找。经典“两数之和（无序数组）”：边遍历边查 target - x 是否已在哈希表里，命中就找到，否则把 x 和它的下标存进去。一次遍历 O(n)。

示例代码

std::unordered_map<int, int> pos;      // 值 -> 下标
for (int i = 0; i < (int)a.size(); ++i) {
    int need = target - a[i];
    if (pos.count(need)) { /* pos[need] 与 i 配对 */ }
    pos[a[i]] = i;
}

⏱ 复杂度　时间复杂度 O(n)，空间 O(n)

⚠️ 易错点　count(key) 只问“在不在”，不插入；用 operator[] 查询会插入默认值。存结构体做键要自定义哈希，麻烦时先用 map 顶住。

✍️ 本节练习

11.3.1必做众数

读入 n 个整数，输出出现次数最多的数（并列时输出较小的）。

输入　第一行 n；第二行 n 个整数。

输出　出现次数最多的数。

样例输入

6
3 1 3 2 3 1

样例输出

💡 提示　unordered_map 计数，遍历时维护最大值。

✅ 查看参考答案与解析

#include <iostream>
#include <unordered_map>
int main() {
    int n;
    std::cin >> n;
    std::unordered_map<int, int> freq;
    int best = 0, bestCnt = -1;
    for (int i = 0; i < n; ++i) {
        int x;
        std::cin >> x;
        int c = ++freq[x];
        if (c > bestCnt || (c == bestCnt && x < best)) {
            bestCnt = c;
            best = x;
        }
    }
    std::cout << best << '\n';
    return 0;
}

解析　哈希计数一趟 O(n)；并列时选较小值要加条件。

11.3.2挑战两数之和（哈希版）

数组不一定有序，找两个数使和等于 target，输出下标（保证唯一解）。要求用哈希表 O(n) 完成。

输入　第一行 n target；第二行 n 个整数（无序）。

输出　两个下标，小的在前。

样例输入

5 9
2 7 11 15 -2

样例输出

0 1

💡 提示　边遍历边存 map<value, index>，查 target - x 在不在。

✅ 查看参考答案与解析

#include <iostream>
#include <unordered_map>
#include <vector>
int main() {
    int n, target;
    std::cin >> n >> target;
    std::vector<int> nums(n);
    for (int i = 0; i < n; ++i) { std::cin >> nums[i]; }
    std::unordered_map<int, int> seen;
    for (int i = 0; i < n; ++i) {
        int need = target - nums[i];
        if (seen.count(need)) {
            int a = seen[need], b = i;
            if (a > b) { std::swap(a, b); }
            std::cout << a << ' ' << b << '\n';
            return 0;
        }
        seen[nums[i]] = i;
    }
    return 0;
}

解析　每个数查“补数”在不在表里——一趟 O(n)，无序也能做。

11.4 前缀和

思想：pre[i] = a[0] + ... + a[i-1]（pre 长度 n+1）。任何区间和 a[l..r] = pre[r+1] - pre[l]，从 O(n) 变 O(1)。

模板与适用场景

适用：大量区间求和查询、和为 k 的子数组计数（配合哈希表）。预处理一遍 O(n)，之后每次查询 O(1)。子数组和 = 两个前缀和之差，这是“和为 k 的子数组”问题的钥匙：数一数前面有多少个 pre[j] 等于 pre[i] - k。

示例代码

std::vector<long long> pre(n + 1, 0);
for (int i = 0; i < n; ++i) { pre[i + 1] = pre[i] + a[i]; }
long long rangeSum = pre[r + 1] - pre[l];       // a[l..r] 的和

⏱ 复杂度　预处理 O(n)，每次查询 O(1)

⚠️ 易错点　用 long long 存前缀和：10^5 个 10^9 相加会溢出 int。pre 的长度是 n+1，pre[0]=0 处理空区间。

✍️ 本节练习

11.4.1必做区间和查询

读入 n 个数和 q 组询问 (l, r)，输出每组 a[l..r] 的和（下标从 0 开始）。

输入　第一行 n；第二行 n 个整数；第三行 q；接下来 q 行每行 l r。

输出　q 行，每行一个区间和。

样例输入

样例输出

15
9
3

💡 提示　pre[r+1] - pre[l]；pre 用 long long。

✅ 查看参考答案与解析

#include <iostream>
#include <vector>
int main() {
    int n;
    std::cin >> n;
    std::vector<int> a(n);
    std::vector<long long> pre(n + 1, 0);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
        pre[i + 1] = pre[i] + a[i];
    }
    int q;
    std::cin >> q;
    while (q--) {
        int l, r;
        std::cin >> l >> r;
        std::cout << pre[r + 1] - pre[l] << '\n';
    }
    return 0;
}

解析　pre[i] = 前 i 个元素的和；区间 [l,r] 和 = pre[r+1] - pre[l]。

11.4.2挑战和为 k 的子数组

读入 n 个整数和 k，统计有多少个连续子数组的和恰好等于 k（元素可正可负）。

输入　第一行 n k；第二行 n 个整数。

输出　子数组个数。

样例输入

5 5
1 2 3 4 5

样例输出

💡 提示　前缀和 + 哈希：遍历时把每个前缀和存进 map，查 pre - k 出现过几次。

✅ 查看参考答案与解析

#include <iostream>
#include <unordered_map>
#include <vector>
int main() {
    int n, k;
    std::cin >> n >> k;
    std::vector<int> a(n);
    for (int i = 0; i < n; ++i) { std::cin >> a[i]; }
    std::unordered_map<long long, int> cnt;
    cnt[0] = 1;               // 空前缀和
    long long pre = 0, ans = 0;
    for (int x : a) {
        pre += x;
        ans += cnt[pre - k];  // 之前有多少个前缀和 = pre - k
        ++cnt[pre];
    }
    std::cout << ans << '\n';
    return 0;
}

解析　子数组和 = 两个前缀和之差；哈希统计差值出现次数，一趟 O(n)。

11.5 二分查找

思想：在单调（或分段单调）的序列里，每次把搜索范围减半，O(log n)。本质不是“在一个数组里找数”，而是“找到最小/最大的满足某个条件的值”。

整数二分的万能写法

标准库有 lower_bound/upper_bound，但手写整数二分的模板必须会：找最小的满足 ok(x) 的 x。区间 [left, right)，每次 mid = left + (right - left) / 2（这样写避免 left + right 溢出），ok(mid) 为真则 right = mid（答案可能更小），否则 left = mid + 1。循环结束时 left == right 就是答案。

示例代码

auto ok = [&](long long x) { return x * x >= n; };  // 例：求平方根上取整
long long left = 0, right = n + 1;
while (left < right) {
    long long mid = left + (right - left) / 2;
    if (ok(mid)) { right = mid; }
    else { left = mid + 1; }
}

⏱ 复杂度　时间复杂度 O(log n)

⚠️ 易错点　统一用 left + (right - left) / 2 防溢出；想清楚区间开闭（用左闭右开最不易错）；答案不存在时要想好 right 的初值。

✍️ 本节练习

11.5.1必做手写 lower_bound

升序数组，用二分找第一个 >= x 的下标，没有输出 -1。不许用 std::lower_bound，手写。

输入　第一行 n x；第二行 n 个升序整数。

输出　下标或 -1。

样例输入

6 4
1 3 3 5 7 9

样例输出

💡 提示　while (l < r) { mid = l + (r - l) / 2; if (a[mid] >= x) r = mid; else l = mid + 1; }

✅ 查看参考答案与解析

#include <iostream>
#include <vector>
int main() {
    int n, x;
    std::cin >> n >> x;
    std::vector<int> a(n);
    for (int i = 0; i < n; ++i) { std::cin >> a[i]; }
    int l = 0, r = n;
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (a[mid] >= x) { r = mid; } else { l = mid + 1; }
    }
    std::cout << (l < n ? l : -1) << '\n';
    return 0;
}

解析　r 初始为 n（开区间）；这个模板就是 std::lower_bound 的手写版，务必背熟。

11.5.2挑战二分求平方根

读入非负整数 x，输出 floor(sqrt(x))，要求用二分答案实现（不许用 sqrt 函数）。

输入　一个整数 x（0 ≤ x ≤ 10^9）。

输出　x 的整数平方根。

样例输入

样例输出

💡 提示　二分 [0, x]，判断 mid*mid 是否 <= x，找最大的满足者。用 long long 防溢出。

✅ 查看参考答案与解析

#include <iostream>
int main() {
    long long x;
    std::cin >> x;
    long long l = 0, r = x + 1;   // 答案在 [0, x]
    while (l < r) {
        long long mid = l + (r - l) / 2;
        if (mid * mid <= x) { l = mid + 1; }   // mid 满足，答案至少是 mid
        else { r = mid; }
    }
    std::cout << l - 1 << '\n';   // 退出时 l 是第一个 mid*mid > x 的数
    return 0;
}

解析　二分答案：把“求值”变成“对每个候选值判断是否可行”，单调即可二分。

11.6 深度优先搜索（DFS）

思想：一条路走到黑，走不通就回头（递归 + 回溯）。本质是递归枚举，适合图、网格、树上的遍历与可达性判断。

网格 DFS 模板与易错点

连通块计数是最经典的入门题：从每个未访问的格子出发 DFS，把整块染色/标记，统计出发次数。模板四步：① 边界检查（出界、已访问、不是目标都返回）；② 标记访问（必须在进入时就标记，否则重复访问死循环）；③ 遍历四个方向；④ 递归调用。

示例代码

const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};
void dfs(int x, int y) {
    if (x < 0 || x >= n || y < 0 || y >= m) { return; }   // 出界
    if (vis[x][y] || grid[x][y] == 0) { return; }          // 已访问/不是目标
    vis[x][y] = true;                                      // 进入即标记
    for (int k = 0; k < 4; ++k) { dfs(x + dx[k], y + dy[k]); }
}

⏱ 复杂度　时间复杂度 O(点数 + 边数)

⚠️ 易错点　访问标记一定要在进入函数时立刻置位，不能等递归返回后再置；用 vector<char> 做标记比 vector<bool> 更少意外。

✍️ 本节练习

11.6.1必做连通块计数

n×m 的 0/1 网格（1 是陆地），用 DFS 统计有多少个连通块（上下左右相连的 1 算一块）。

输入　第一行 n m；接下来 n 行，每行 m 个字符（0 或 1）。

输出　连通块数量。

样例输入

样例输出

💡 提示　四方向 dx/dy；每遇到未访问的 1 就 DFS 标记整块。

✅ 查看参考答案与解析

#include <iostream>
#include <string>
#include <vector>
int n, m;
std::vector<std::string> grid;
std::vector<std::vector<char>> vis;
const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};
void dfs(int x, int y) {
    vis[x][y] = 1;
    for (int k = 0; k < 4; ++k) {
        int nx = x + dx[k], ny = y + dy[k];
        if (nx >= 0 && nx < n && ny >= 0 && ny < m
            && !vis[nx][ny] && grid[nx][ny] == '1') {
            dfs(nx, ny);
        }
    }
}
int main() {
    std::cin >> n >> m;
    grid.resize(n);
    vis.assign(n, std::vector<char>(m, 0));
    for (int i = 0; i < n; ++i) { std::cin >> grid[i]; }
    int blocks = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (grid[i][j] == '1' && !vis[i][j]) {
                ++blocks;
                dfs(i, j);
            }
        }
    }
    std::cout << blocks << '\n';
    return 0;
}

解析　模板：外层找入口 → DFS 标记整块 → 计数。边界检查不能少。

11.6.2挑战路径计数

n×m 网格（0 可走、1 是墙），从 (0,0) 走到 (n-1,m-1)，每次只能向右或向下，输出不同路径数（保证 ≤ 10^9）。

输入　第一行 n m；接下来 n 行每行 m 个字符。

输出　路径数。

样例输入

样例输出

💡 提示　DFS 只有右、下两个方向；终止条件到终点返回 1，越界/墙返回 0。

✅ 查看参考答案与解析

#include <iostream>
#include <string>
#include <vector>
int n, m;
std::vector<std::string> grid;
long long dfs(int x, int y) {
    if (x == n - 1 && y == m - 1) { return 1; }
    long long ways = 0;
    if (x + 1 < n && grid[x + 1][y] == '0') { ways += dfs(x + 1, y); }
    if (y + 1 < m && grid[x][y + 1] == '0') { ways += dfs(x, y + 1); }
    return ways;
}
int main() {
    std::cin >> n >> m;
    grid.resize(n);
    for (int i = 0; i < n; ++i) { std::cin >> grid[i]; }
    std::cout << dfs(0, 0) << '\n';
    return 0;
}

解析　只右/下两个方向所以天然无环，不需要访问标记；这是 DFS 计数的最简模型。

11.7 广度优先搜索（BFS）

思想：一层一层向外扩散，配合队列。第一个到达某个点的层数一定是最短步数——所以 BFS 是“无权图最短路”的标准答案。

BFS 模板

队列初始化装起点，dist 数组记录步数（-1 表示未访问）。循环：取队首 → 遍历邻居 → 未访问的邻居记录 dist 并入队。因为一层层扩散，第一次给某点赋的 dist 就是最短。

示例代码

std::queue<std::pair<int, int>> q;
std::vector<std::vector<int>> dist(n, std::vector<int>(m, -1));
dist[sx][sy] = 0;
q.push({sx, sy});
while (!q.empty()) {
    auto [x, y] = q.front(); q.pop();
    for (int k = 0; k < 4; ++k) {
        int nx = x + dx[k], ny = y + dy[k];
        if (nx >= 0 && nx < n && ny >= 0 && ny < m && dist[nx][ny] == -1) {
            dist[nx][ny] = dist[x][y] + 1;
            q.push({nx, ny});
        }
    }
}

⏱ 复杂度　时间复杂度 O(点数 + 边数)

⚠️ 易错点　和 DFS 不同，BFS 用 dist == -1 当“未访问”标记，天然保证第一次就是最短。需要路径时另开 parent 数组。

图 6：BFS 按层扩散，第一次到达就是最短步数

✍️ 本节练习

11.7.1必做迷宫最短步数

n×m 迷宫（0 可走、1 是墙），从 (0,0) 到 (n-1,m-1) 最少走多少步（四方向），走不到输出 -1。

输入　第一行 n m；接下来 n 行每行 m 个字符。

输出　最少步数或 -1。

样例输入

样例输出

💡 提示　dist 数组记录步数（-1 表示未访问）；入队即标记。

✅ 查看参考答案与解析

#include <iostream>
#include <queue>
#include <string>
#include <utility>
#include <vector>
int main() {
    int n, m;
    std::cin >> n >> m;
    std::vector<std::string> maze(n);
    for (int i = 0; i < n; ++i) { std::cin >> maze[i]; }
    const int dx[4] = {-1, 1, 0, 0};
    const int dy[4] = {0, 0, -1, 1};
    std::vector<std::vector<int>> dist(n, std::vector<int>(m, -1));
    std::queue<std::pair<int, int>> q;
    dist[0][0] = 0;
    q.push({0, 0});
    while (!q.empty()) {
        auto [x, y] = q.front(); q.pop();
        for (int k = 0; k < 4; ++k) {
            int nx = x + dx[k], ny = y + dy[k];
            if (nx >= 0 && nx < n && ny >= 0 && ny < m
                && dist[nx][ny] == -1 && maze[nx][ny] == '0') {
                dist[nx][ny] = dist[x][y] + 1;
                q.push({nx, ny});
            }
        }
    }
    std::cout << dist[n - 1][m - 1] << '\n';
    return 0;
}

解析　dist 兼作步数记录和访问标记；BFS 第一次到达就是最短步数。

11.7.2挑战BFS 连通块

用 BFS（队列）而不是 DFS 重写连通块计数：n×m 网格数 1 的连通块。

输入　第一行 n m；接下来 n 行每行 m 个字符。

输出　连通块数量。

样例输入

样例输出

💡 提示　外层循环找未访问的 1，用队列扩展整块。

✅ 查看参考答案与解析

#include <iostream>
#include <queue>
#include <string>
#include <utility>
#include <vector>
int main() {
    int n, m;
    std::cin >> n >> m;
    std::vector<std::string> grid(n);
    for (int i = 0; i < n; ++i) { std::cin >> grid[i]; }
    const int dx[4] = {-1, 1, 0, 0};
    const int dy[4] = {0, 0, -1, 1};
    std::vector<std::vector<char>> vis(n, std::vector<char>(m, 0));
    int blocks = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (grid[i][j] == '1' && !vis[i][j]) {
                ++blocks;
                std::queue<std::pair<int, int>> q;
                q.push({i, j});
                vis[i][j] = 1;
                while (!q.empty()) {
                    auto [x, y] = q.front(); q.pop();
                    for (int k = 0; k < 4; ++k) {
                        int nx = x + dx[k], ny = y + dy[k];
                        if (nx >= 0 && nx < n && ny >= 0 && ny < m
                            && !vis[nx][ny] && grid[nx][ny] == '1') {
                            vis[nx][ny] = 1;
                            q.push({nx, ny});
                        }
                    }
                }
            }
        }
    }
    std::cout << blocks << '\n';
    return 0;
}

解析　DFS 和 BFS 都能数连通块：区别只在扩展顺序（递归栈 vs 队列），模板思想相通。

11.8 回溯

思想：DFS 的一种：每一步尝试所有选择，走不通就撤销选择（回退）换下一个。全排列、组合、子集、八皇后都是它。

排列模板：选择 + 递归 + 撤销

全排列模板：path 记录当前排列，used 记录用过哪些数。每层从没用过的数里挑一个放进 path，递归，返回后从 path 里弹出并取消标记（撤销）。“撤销”是回溯的灵魂——不撤销，下一次尝试就带着上一次的残留。

示例代码

void dfs(std::vector<int>& path, std::vector<char>& used) {
    if ((int)path.size() == n) { /* 得到一个排列，记录 */ return; }
    for (int i = 0; i < n; ++i) {
        if (used[i]) { continue; }
        used[i] = true;
        path.push_back(a[i]);
        dfs(path, used);
        path.pop_back();      // 撤销
        used[i] = false;      // 撤销
    }
}

⏱ 复杂度　时间复杂度 O(n! × n)（排列数）

⚠️ 易错点　一定要“两步对称”：递归前 push + 标记，递归后 pop + 取消标记，缺一步答案就错或重复。

✍️ 本节练习

11.8.1必做全排列

读入 n（≤8），输出 1..n 的所有全排列，每行一个，数字空格分隔。

输入　一个整数 n。

输出　所有全排列，每行一个。

样例输入

样例输出

💡 提示　used 标记 + path 数组 + 递归深度终止；递归后撤销 used。

✅ 查看参考答案与解析

#include <iostream>
#include <vector>
int n;
std::vector<int> path;
std::vector<char> used;
void dfs(int depth) {
    if (depth == n) {
        for (int i = 0; i < n; ++i) { std::cout << path[i] << ' '; }
        std::cout << '\n';
        return;
    }
    for (int i = 1; i <= n; ++i) {
        if (used[i]) { continue; }
        used[i] = 1;
        path[depth] = i;
        dfs(depth + 1);
        used[i] = 0;   // 撤销
    }
}
int main() {
    std::cin >> n;
    path.resize(n);
    used.assign(n + 1, 0);
    dfs(0);
    return 0;
}

解析　“选 - 递归 - 撤销”三步缺一不可；撤销是回溯的灵魂。

11.8.2挑战组合 C(n, k)

读入 n、k（n ≤ 8），输出从 1..n 中选 k 个数的所有组合，每个组合一行，升序，组合之间按字典序。

输入　一行 n k。

输出　所有组合，每行一个。

样例输入

4 2

样例输出

💡 提示　从 start 开始选，保证升序不重；选了 k 个就输出。

✅ 查看参考答案与解析

#include <iostream>
#include <vector>
int n, k;
std::vector<int> path;
void dfs(int start, int cnt) {
    if (cnt == k) {
        for (int i = 0; i < k; ++i) { std::cout << path[i] << ' '; }
        std::cout << '\n';
        return;
    }
    for (int i = start; i <= n; ++i) {
        path[cnt] = i;
        dfs(i + 1, cnt + 1);   // 下一个从 i+1 开始，天然不重复
    }
}
int main() {
    std::cin >> n >> k;
    path.resize(k);
    dfs(1, 0);
    return 0;
}

解析　组合和排列的区别：从 start 开始选，后续只选更大的数，避免重复排列。

11.9 贪心

思想：每一步都做“当前看起来最优”的选择，并且证明局部最优能推出全局最优。贪心不是试出来的，是要证明的。

区间调度：先按结束时间排序

经典问题“最多不重叠区间”：按结束时间从小到大排序，依次选“结束最早且和已选不相交”的区间。为什么按结束时间？因为结束得越早，给后面的区间留的空间越大。排序 + 一次扫描，O(n log n)。

示例代码

std::sort(a.begin(), a.end(),
          [](const Interval& x, const Interval& y) { return x.r < y.r; });
int cnt = 0, last = -1;
for (const auto& seg : a) {
    if (seg.l >= last) { ++cnt; last = seg.r; }   // 不相交才选
}

⏱ 复杂度　时间复杂度 O(n log n)（排序主导）

⚠️ 易错点　贪心要证明：反例不存在（或举出反例说明不成立）。拿不准时改用 DP 或枚举。

✍️ 本节练习

11.9.1必做区间调度

读入 n 个区间 (l, r)，输出最多能选多少个互不重叠的区间。

输入　第一行 n；接下来 n 行每行 l r。

输出　最大区间数。

样例输入

样例输出

💡 提示　按结束时间升序排序，依次选结束最早且不冲突的。

✅ 查看参考答案与解析

#include <algorithm>
#include <iostream>
#include <vector>
struct Seg { int l, r; };
int main() {
    int n;
    std::cin >> n;
    std::vector<Seg> segs(n);
    for (int i = 0; i < n; ++i) { std::cin >> segs[i].l >> segs[i].r; }
    std::sort(segs.begin(), segs.end(),
              [](const Seg& a, const Seg& b) { return a.r < b.r; });
    int cnt = 0, lastEnd = -1;
    for (const auto& s : segs) {
        if (s.l >= lastEnd) { ++cnt; lastEnd = s.r; }
    }
    std::cout << cnt << '\n';
    return 0;
}

解析　结束得越早给后面留越多空间——可证明最优的经典贪心。

11.9.2挑战找零钱

有面值 50、20、10、5、1 元的纸币（数量无限），读入金额 x，输出凑出 x 元所需的最少纸币数。

输入　一个整数 x（1 ≤ x ≤ 10^9）。

输出　最少纸币数。

样例输入

样例输出

💡 提示　从大面值往小面值贪心：50+20+20+1+1+1 = 6 张。

✅ 查看参考答案与解析

#include <iostream>
int main() {
    int x;
    std::cin >> x;
    int values[5] = {50, 20, 10, 5, 1};
    int cnt = 0;
    for (int v : values) {
        cnt += x / v;
        x %= v;
    }
    std::cout << cnt << '\n';
    return 0;
}

解析　这套面值下贪心最优（大面值整除小面值）；注意贪心不是任何找零都最优，用前要验证。

11.10 动态规划（DP）

思想：把大问题拆成重叠的小问题，用数组把子问题的答案存起来，避免重复计算。三步走：定义状态 → 写转移方程 → 定初值与答案。

爬楼梯：DP 最小模型

f[i] = 到第 i 级台阶的方法数。f[1] = 1，f[2] = 2，f[i] = f[i-1] + f[i-2]（最后一步要么跨 1 级要么跨 2 级）。这就是状态（f[i] 的含义）、转移（从哪来）、初值（边界）三件套。最大子段和是另一个高频模型：end[i] = max(end[i-1] + a[i], a[i])。

示例代码

std::vector<int> f(n + 1);
f[1] = 1; f[2] = 2;                     // 初值
for (int i = 3; i <= n; ++i) {
    f[i] = f[i - 1] + f[i - 2];         // 转移
}
std::cout << f[n];                       // 答案

⏱ 复杂度　时间复杂度 O(n)，空间可优化到 O(1)

⚠️ 易错点　写 DP 先写对状态含义和转移，再想优化。空间优化（滚动数组）是最后一步，别一开始就为了省空间写错。

✍️ 本节练习

11.10.1必做爬楼梯

爬 n 阶楼梯，一次可以上 1 阶或 2 阶，输出一共有多少种不同的爬法（结果可能很大，用 long long）。

输入　一个整数 n（1 ≤ n ≤ 90）。

输出　方法数。

样例输入

样例输出

💡 提示　f[1]=1, f[2]=2, f[i]=f[i-1]+f[i-2]。

✅ 查看参考答案与解析

#include <iostream>
#include <vector>
int main() {
    int n;
    std::cin >> n;
    if (n <= 2) { std::cout << n << '\n'; return 0; }
    std::vector<long long> f(n + 1);
    f[1] = 1;
    f[2] = 2;
    for (int i = 3; i <= n; ++i) { f[i] = f[i - 1] + f[i - 2]; }
    std::cout << f[n] << '\n';
    return 0;
}

解析　DP 最小可运行模型：初始值 + 转移方程 + 目标状态。n=90 结果超 int，必须 long long。

11.10.2挑战最大子段和

读入 n 个整数（可正可负），输出最大连续子段和（至少选一个数）。

输入　第一行 n；第二行 n 个整数。

输出　最大子段和。

样例输入

9
-2 1 -3 4 -1 2 1 -5 4

样例输出

💡 提示　经典 DP：dp[i] = max(a[i], dp[i-1] + a[i])，答案取所有 dp 的最大值。

✅ 查看参考答案与解析

#include <algorithm>
#include <iostream>
#include <vector>
int main() {
    int n;
    std::cin >> n;
    std::vector<long long> a(n);
    for (int i = 0; i < n; ++i) { std::cin >> a[i]; }
    long long best = a[0], cur = a[0];
    for (int i = 1; i < n; ++i) {
        cur = std::max(a[i], cur + a[i]);   // 重新开始 or 延续上一段
        best = std::max(best, cur);
    }
    std::cout << best << '\n';
    return 0;
}

解析　状态是“以 i 结尾的最大子段和”；要么自己开头，要么接上前一段。空间可压缩成两个变量。

解析　用法：每天完成 2 个单元，每道编程题写完、编译、跑通样例后在“完成”列打 √；正确率 = 一次跑通的题目数 / 当天题目数；错题抄进附录 B。“复习”列在第 3 天和第 7 天勾掉对应单元（重做做错的题）。每周日晚做一次周复盘：把连续错两次的题重写一遍。

解析　用法：每道没一次跑通的题填一行。错误原因从“编译报错 / 结果不对 / 边界没考虑 / 超时 / 粗心”里选；第 3 天和第 7 天重做时能不看答案写对，就在“已掌握”打 √。

本章小结

双指针：有序数组两端向内，O(n)；滑动窗口：连续子数组/子串，右进左出。
哈希表：查找 O(1)，两数之和第一反应；前缀和：区间和 O(1)，配合哈希数子数组。
二分：找最小/最大满足条件的值，mid = left + (right-left)/2 防溢出。
DFS 进点即标记；BFS 队列求无权最短路；回溯递归后必须撤销；贪心要先证明；DP 先定义状态再写转移。

🧩 本章综合练习

这几道题把本章多个知识点串起来，建议合上资料独立完成，再展开答案对照。

11.A综合一数组三问：DP + 前缀和哈希 + 哈希配对

读入 n 个数和 target，输出三行：最大子段和（DP）；和为 0 的连续子数组个数（前缀和 + 哈希）；是否存在两个数之和等于 target（哈希，输出 yes/no）。

输入　第一行 n target；第二行 n 个整数。

输出　三行：最大子段和、和为 0 的子数组个数、yes 或 no。

样例输入

6 9
1 -2 3 -2 5 -1

样例输出

6
1
no

💡 提示　三种思想各管一行输出：DP 求最大子段和、前缀和 + 哈希计数、哈希查补数。

✅ 查看参考答案与解析

#include <algorithm>
#include <iostream>
#include <unordered_map>
#include <vector>

int main() {
    int n{}, target{};
    std::cin >> n >> target;
    std::vector<long long> a(n);
    for (int i = 0; i < n; ++i) { std::cin >> a[i]; }

    // 1) 最大子段和（DP）
    long long best = a[0], cur = a[0];
    for (int i = 1; i < n; ++i) {
        cur = std::max(a[i], cur + a[i]);
        best = std::max(best, cur);
    }
    std::cout << best << '\n';

    // 2) 和为 0 的连续子数组个数（前缀和 + 哈希）
    std::unordered_map<long long, long long> cnt;
    cnt[0] = 1;
    long long pre = 0, ans = 0;
    for (int i = 0; i < n; ++i) {
        pre += a[i];
        ans += cnt[pre];      // 之前出现过多少次同样的前缀和
        ++cnt[pre];
    }
    std::cout << ans << '\n';

    // 3) 两数之和（哈希查补数）
    std::unordered_map<long long, int> seen;
    bool found = false;
    for (int i = 0; i < n; ++i) {
        if (seen.count(target - a[i])) { found = true; break; }
        ++seen[a[i]];
    }
    std::cout << (found ? "yes" : "no") << '\n';
    return 0;
}

解析　同一份输入上跑三种思想很常见：先读数据，再分别处理，最后逐行输出。

11.B综合网格综合：BFS 最短路 + DFS 连通块

读入 n×m 的 0/1 网格（0 可走，1 是墙），输出两行：从左上角到右下角的最短步数（四方向，不可达输出 -1）；网格中 1 的连通块个数。BFS 和 DFS 一次写全。

输入　第一行 n m；接下来 n 行，每行 m 个字符（0 或 1）。

输出　第一行 steps=最少步数；第二行 blocks=连通块数。

样例输入

样例输出

steps=4
blocks=1

💡 提示　BFS 入队即标记（dist == -1 表示未访问）；DFS 用递归 lambda 时要把它自己传进去（auto&& self）。

✅ 查看参考答案与解析

#include <iostream>
#include <queue>
#include <string>
#include <utility>
#include <vector>

int main() {
    int n{}, m{};
    std::cin >> n >> m;
    std::vector<std::string> g(n);
    for (int i = 0; i < n; ++i) { std::cin >> g[i]; }

    const int dx[4] = {-1, 1, 0, 0};
    const int dy[4] = {0, 0, -1, 1};

    // 1) BFS：无权图最短路
    std::vector<std::vector<int>> dist(n, std::vector<int>(m, -1));
    std::queue<std::pair<int, int>> q;
    if (g[0][0] == '0') {
        dist[0][0] = 0;
        q.push({0, 0});
    }
    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        for (int k = 0; k < 4; ++k) {
            int nx = x + dx[k], ny = y + dy[k];
            if (nx >= 0 && nx < n && ny >= 0 && ny < m &&
                g[nx][ny] == '0' && dist[nx][ny] == -1) {
                dist[nx][ny] = dist[x][y] + 1;
                q.push({nx, ny});
            }
        }
    }
    std::cout << "steps=" << dist[n - 1][m - 1] << '\n';

    // 2) DFS：连通块计数
    std::vector<std::vector<char>> vis(n, std::vector<char>(m, 0));
    auto dfs = [&](auto&& self, int x, int y) -> void {
        vis[x][y] = 1;
        for (int k = 0; k < 4; ++k) {
            int nx = x + dx[k], ny = y + dy[k];
            if (nx >= 0 && nx < n && ny >= 0 && ny < m &&
                !vis[nx][ny] && g[nx][ny] == '1') {
                self(self, nx, ny);
            }
        }
    };
    int blocks = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (g[i][j] == '1' && !vis[i][j]) {
                ++blocks;
                dfs(dfs, i, j);
            }
        }
    }
    std::cout << "blocks=" << blocks << '\n';
    return 0;
}

解析　BFS 第一次到达某点就是最短，DFS 只回答“能不能到、属于哪一块”。两个模板的边界检查要背熟。

📚 本文概念都在知识大全：

双指针 · 滑动窗口 · 哈希表 · 前缀和 · 二分查找 · DFS · BFS · 回溯 · 贪心 · 动态规划 · 时间复杂度

← 上一章：第 10 章动手写数据结构下一章：第 12 章调试、构建与测试 →