📖 第 6.2 章 ⏱️ 约 110 分钟 🎯 进阶

第 6.2 章：经典 DP 问题

📝 前置条件： 确保掌握了第 6.1 章的核心 DP 概念——状态、递推和初始条件。你应该能从零实现斐波那契和基本硬币找零。

本章我们处理竞赛编程中最重要、应用最广泛的三个 DP 问题。掌握这些模式将帮助你识别并解决数十道 USACO 题目。

6.2.1 最长递增子序列（LIS）

题目： 给定 N 个整数的数组 A，找最长的严格递增子序列的长度。子序列不需要连续。

示例： A = [3, 1, 8, 2, 5]

LIS：[1, 2, 5] → 长度 3
或：[3, 8] → 长度 2（不是最长）

💡 核心思路： 子序列可以跳过元素，但必须保持相对顺序。关键 DP 洞察：对每个下标 i，问「以 A[i] 结尾的最长递增子序列是什么？」然后对所有 i 取最大值就是答案。

LIS 状态转移——A = [3, 1, 8, 2, 5]：

LIS State Transitions

💡 转移规则： dp[i] = 1 + max(dp[j])（对所有 j < i 且 A[j] < A[i]）。每条箭头表示「以 j 结尾的子序列可以延伸到包含 i」。

LIS Visualization

`O(N²)` DP 解法

状态： dp[i] = 以下标 i 结尾的最长递增子序列长度
递推： dp[i] = 1 + max(对所有 j < i 且 A[j] < A[i] 的 dp[j])
初始条件： dp[i] = 1（只含 A[i] 自身的子序列）
答案： max(dp[0], dp[1], ..., dp[N-1])

对 A = [3, 1, 8, 2, 5] 的逐步追踪：

dp[0] = 1  (以 3 结尾的 LIS：只有 [3])
dp[1] = 1  (以 1 结尾的 LIS：只有 [1])
dp[2] = 2  (以 8 结尾的 LIS：[3,8] 或 [1,8])
dp[3] = 2  (以 2 结尾的 LIS：[1,2])
dp[4] = 3  (以 5 结尾的 LIS：[1,2,5])

LIS 长度 = max(dp) = 3

📄 C++ 完整代码

// LIS O(N²) — 简单但 N > 5000 时太慢
#include <bits/stdc++.h>
using namespace std;

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

    int n;
    cin >> n;
    vector<int> A(n);
    for (int &x : A) cin >> x;

    vector<int> dp(n, 1);  // 每个元素单独是长度为 1 的子序列

    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (A[j] < A[i]) {              // A[j] 可以延伸到 A[i]
                dp[i] = max(dp[i], dp[j] + 1);  // ← 关键行
            }
        }
    }

    cout << *max_element(dp.begin(), dp.end()) << "\n";
    return 0;
}

样例输入： 5 / 3 1 8 2 5 → 输出： 3

复杂度分析：

时间： O(N²) —— 双重循环
空间： O(N) —— dp 数组

N ≤ 5000 时 O(N²) 够快，N 最大 10^5 时需要 O(N log N) 方案。

`O(N log N)` LIS（耐心排序）

关键思路：维护 tails 数组，其中 tails[k] = 迄今为止任意长度为 k+1 的递增子序列中最小可能的尾部元素。

💡 核心思路（耐心排序）： 想象把牌发到若干叠（像接龙游戏）。每叠是递减序列，一张牌放到顶牌 ≥ 它的最左侧那叠。若无这样的叠，开一叠新的。牌的叠数就等于 LIS 长度！tails 数组正是这些叠的顶牌。

对 A = [3, 1, 8, 2, 5] 的逐步追踪：

处理 3：tails=[]，无元素 ≥ 3，追加：tails=[3]
处理 1：tails=[3]，lower_bound(1) 在下标 0（3 ≥ 1），替换：tails=[1]
处理 8：tails=[1]，lower_bound(8) 到末尾，追加：tails=[1,8]
处理 2：tails=[1,8]，lower_bound(2) 在下标 1（8 ≥ 2），替换：tails=[1,2]
处理 5：tails=[1,2]，lower_bound(5) 到末尾，追加：tails=[1,2,5]
答案 = tails.size() = 3

📄 C++ 完整代码

// LIS O(N log N) — N 最大 10^5 时够快
#include <bits/stdc++.h>
using namespace std;

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

    int n;
    cin >> n;
    vector<int> A(n);
    for (int &x : A) cin >> x;

    vector<int> tails;  // tails[i] = 长度为 i+1 的 IS 的最小尾元素

    for (int x : A) {
        // 找第一个 tails[pos] >= x（严格递增用 lower_bound）
        auto it = lower_bound(tails.begin(), tails.end(), x);

        if (it == tails.end()) {
            tails.push_back(x);   // x 延伸了最长子序列
        } else {
            *it = x;              // ← 关键行：替换以保持最小可能尾部
        }
    }

    cout << tails.size() << "\n";
    return 0;
}

⚠️ 注意： tails 不存储实际的 LIS 元素，只存储其长度。 lower_bound 给出严格递增的 LIS（A[j] < A[i]）；若需不减序列（A[j] ≤ A[i]），改用 upper_bound。

复杂度： O(N log N) 时间，O(N) 空间。

6.2.2 0/1 背包问题

题目： 有 N 件物品，物品 i 的重量为 w[i]，价值为 v[i]。背包最多承重 W，选择物品使总价值最大，每件物品最多选一次（0/1 = 拿或不拿）。

图示：背包 DP 表

二维表展示了 dp[物品][容量]，每行加入一件物品，答案在右下角。

Knapsack DP Table

DP 公式

0/1 背包决策——拿或不拿物品 i：

Knapsack Decision

💡 与无界背包的关键区别： 因为每件物品只能用一次，「拿」时从行 dp[i-1] 读取，而不是当前行。这就是为什么一维优化版本要反向迭代重量。

状态： dp[i][w] = 使用物品 1..i 且总重量 ≤ w 时的最大价值
递推：
- 不拿物品 i：dp[i][w] = dp[i-1][w]
- 拿物品 i（仅在 w[i] ≤ w 时）：dp[i][w] = dp[i-1][w - weight[i]] + value[i]
- 取最大值

📄 C++ 完整代码

#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> weight(n + 1), value(n + 1);
    for (int i = 1; i <= n; i++) cin >> weight[i] >> value[i];

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

    for (int i = 1; i <= n; i++) {
        for (int w = 0; w <= W; w++) {
            dp[i][w] = dp[i-1][w];  // 选项一：不拿物品 i

            if (weight[i] <= w) {    // 选项二：拿物品 i（如果放得下）
                dp[i][w] = max(dp[i][w], dp[i-1][w - weight[i]] + value[i]);
            }
        }
    }

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

空间优化的 0/1 背包——`O(W)` 空间

只需要上一行 dp[i-1]，可以用一维数组。关键： w 从 W 倒序迭代（否则物品 i 会被使用多次）：

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

for (int i = 1; i <= n; i++) {
    // 倒序迭代，防止物品 i 被使用多次
    for (int w = W; w >= weight[i]; w--) {
        dp[w] = max(dp[w], dp[w - weight[i]] + value[i]);
    }
}

cout << dp[W] << "\n";

为什么倒序？ 计算 dp[w] 时，需要上一件物品行的 dp[w - weight[i]]。倒序迭代确保 dp[w - weight[i]] 还没被当前物品 i 更新过。

无界背包（物品无限次可用）

若每件物品可以使用多次，改为正序迭代：

for (int i = 1; i <= n; i++) {
    for (int w = weight[i]; w <= W; w++) {  // 正序——允许重复使用
        dp[w] = max(dp[w], dp[w - weight[i]] + value[i]);
    }
}

6.2.3 网格路径计数

题目： 统计从网格左上角 (1,1) 到右下角 (N,M) 只向右或向下移动的路径数，部分格子被堵塞。

图示：网格路径 DP 值

Grid DP

每个格子展示了从 (0,0) 到该格子的路径数。递推 dp[i][j] = dp[i-1][j] + dp[i][j-1] 叠加了从上方和左方到达的路径。

📄 C++ 完整代码

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

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

    int n, m;
    cin >> n >> m;

    vector<string> grid(n);
    for (int r = 0; r < n; r++) cin >> grid[r];

    // dp[r][c] = 到达 (r, c) 的路径数
    vector<vector<long long>> dp(n, vector<long long>(m, 0));

    // 初始条件：起始格子（若不堵塞）
    if (grid[0][0] != '#') dp[0][0] = 1;

    // 填充第一行（只能从左来）
    for (int c = 1; c < m; c++) {
        if (grid[0][c] != '#') dp[0][c] = dp[0][c-1];
    }

    // 填充第一列（只能从上来）
    for (int r = 1; r < n; r++) {
        if (grid[r][0] != '#') dp[r][0] = dp[r-1][0];
    }

    // 填充其余格子
    for (int r = 1; r < n; r++) {
        for (int c = 1; c < m; c++) {
            if (grid[r][c] == '#') {
                dp[r][c] = 0;  // 堵塞——无路径经过此处
            } else {
                dp[r][c] = dp[r-1][c] + dp[r][c-1];  // 从上 + 从左
            }
        }
    }

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

网格最大价值路径

题目： 找从 (1,1) 到 (N,M)（只向右或向下）最大化路径上值之和的路径。

📄 C++ 完整代码

// ...读取 val[r][c]...
vector<vector<long long>> dp(n, vector<long long>(m, 0));
dp[0][0] = val[0][0];

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

for (int r = 1; r < n; r++) {
    for (int c = 1; c < m; c++) {
        dp[r][c] = max(dp[r-1][c], dp[r][c-1]) + val[r][c];
    }
}

cout << dp[n-1][m-1] << "\n";

6.2.4 USACO DP 示例：牛蹄剪刀布

题目（USACO 2019 January Silver）： Bessie 玩 N 局牛蹄剪刀布（类似石头剪刀布）。她事先知道对手的出法，可以最多换 K 次手势，最大化获胜局数。

状态： dp[j][g] = 前 i 局换了 j 次、当前出手势 g 时的最大获胜数。

📄 C++ 完整代码

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

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

    int n, k;
    cin >> n >> k;

    // 0=牛蹄, 1=纸, 2=剪刀
    vector<int> opp(n + 1);
    for (int i = 1; i <= n; i++) {
        char c; cin >> c;
        if (c == 'H') opp[i] = 0;
        else if (c == 'P') opp[i] = 1;
        else opp[i] = 2;
    }

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

    // 初始化：第 1 局前，换了 0 次，任何起始手势
    for (int g = 0; g < 3; g++) dp[0][g] = 0;

    for (int i = 1; i <= n; i++) {
        vector<vector<int>> ndp(k + 1, vector<int>(3, NEG_INF));

        for (int j = 0; j <= k; j++) {
            for (int g = 0; g < 3; g++) {
                if (dp[j][g] == NEG_INF) continue;

                int win = (g == opp[i]) ? 1 : 0;

                // 选项一：不换手势
                ndp[j][g] = max(ndp[j][g], dp[j][g] + win);

                // 选项二：换手势（消耗 1 次）
                if (j < k) {
                    for (int ng = 0; ng < 3; ng++) {
                        if (ng != g) {
                            int nwin = (ng == opp[i]) ? 1 : 0;
                            ndp[j+1][ng] = max(ndp[j+1][ng], dp[j][g] + nwin);
                        }
                    }
                }
            }
        }

        dp = ndp;
    }

    int ans = 0;
    for (int j = 0; j <= k; j++)
        for (int g = 0; g < 3; g++)
            ans = max(ans, dp[j][g]);

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

6.2.5 区间 DP——矩阵链乘法与气球爆破模式

区间 DP 是一种强大的 DP 技术，状态代表连续的子数组或子范围，我们将更小区间的解组合来解决更大的区间。

💡 核心思路： 当区间 [l, r] 的最优解依赖于如何在某个点 k 分割该区间，且子问题 [l, k] 和 [k+1, r] 相互独立时，适用区间 DP。

区间 DP 框架

区间 DP 填充顺序——必须按区间长度递增填充：

Interval DP Fill Order

💡 填充顺序很关键： 必须按区间长度递增填充。计算 dp[l][r] 时，所有更短的子区间 dp[l][k] 和 dp[k+1][r] 必须已经计算好。

状态：    dp[l][r] = 区间 [l, r] 上子问题的最优解
初始条件：dp[i][i] = 单个元素的代价/价值（通常为 0 或平凡值）
顺序：    按区间长度递增填充（len = 1, 2, 3, ..., n）
          确保 dp[l][k] 和 dp[k+1][r] 在 dp[l][r] 之前计算
转移：    dp[l][r] = 对 [l, r-1] 中所有分割点 k 的 min/max：
                    dp[l][k] + dp[k+1][r] + cost(l, k, r)
答案：    dp[1][n]（0-indexed 则为 dp[0][n-1]）

经典示例：矩阵链乘法

题目： 给定 N 个矩阵 A₁, A₂, ..., Aₙ，矩阵 Aᵢ 维度为 dim[i-1] × dim[i]，找最小化标量乘法次数的括号化方案。

状态： dp[l][r] = 计算乘积 Aₗ × Aₗ₊₁ × ... × Aᵣ 的最少乘法次数

转移： 尝试每个分割点 k ∈ [l, r-1]：

左乘积 Aₗ...Aₖ 代价 dp[l][k]，结果维度 dim[l-1] × dim[k]
右乘积 Aₖ₊₁...Aᵣ 代价 dp[k+1][r]，结果维度 dim[k] × dim[r]
两结果相乘代价 dim[l-1] × dim[k] × dim[r]

📄 C++ 完整代码

// 矩阵链乘法 — O(N³) 时间，O(N²) 空间
#include <bits/stdc++.h>
using namespace std;

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

    int n;
    cin >> n;

    vector<int> dim(n + 1);
    for (int i = 0; i <= n; i++) cin >> dim[i];

    vector<vector<long long>> dp(n + 1, vector<long long>(n + 1, 0));
    const long long INF = 1e18;

    // 按区间长度递增填充
    for (int len = 2; len <= n; len++) {
        for (int l = 1; l + len - 1 <= n; l++) {
            int r = l + len - 1;
            dp[l][r] = INF;

            for (int k = l; k < r; k++) {
                long long cost = dp[l][k]
                               + dp[k+1][r]
                               + (long long)dim[l-1] * dim[k] * dim[r];
                dp[l][r] = min(dp[l][r], cost);
            }
        }
    }

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

复杂度： O(N³) 时间，O(N²) 空间。

区间 DP 通用模板

📄 查看代码：区间 DP 通用模板

// 通用区间 DP 模板
void intervalDP(int n) {
    vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));

    // 初始条件：长度为 1 的区间
    for (int i = 1; i <= n; i++) dp[i][i] = base_case(i);

    // 按长度递增填充
    for (int len = 2; len <= n; len++) {
        for (int l = 1; l + len - 1 <= n; l++) {
            int r = l + len - 1;
            dp[l][r] = INF;

            for (int k = l; k < r; k++) {
                int val = dp[l][k] + dp[k+1][r] + cost(l, k, r);
                dp[l][r] = min(dp[l][r], val);
            }
        }
    }
}

⚠️ 常见错误： 以左端点 l 为外层循环、长度为内层循环——这是错误的！计算 dp[l][r] 时，子区间 dp[l][k] 和 dp[k+1][r] 必须已经计算好。始终以长度为外层循环。

6.2.6 分组背包

题目： N 组物品，第 i 组有 cnt[i] 件物品，每组最多选一件（或不选）。在重量 W 内最大化总价值。

💡 与 0/1 背包的关键区别： 0/1 背包逐件物品做决策；分组背包逐组做决策——每组中选哪件（如果选的话）。

📄 C++ 完整代码

#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<vector<pair<int,int>>> groups(n);
    for (int i = 0; i < n; i++) {
        int cnt; cin >> cnt;
        groups[i].resize(cnt);
        for (auto& [w, v] : groups[i]) cin >> w >> v;
    }

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

    for (int i = 0; i < n; i++) {          // 对每组
        for (int w = W; w >= 0; w--) {     // 容量**降序**迭代
            for (auto [wi, vi] : groups[i]) { // 尝试组内每件物品
                if (w >= wi)
                    dp[w] = max(dp[w], dp[w - wi] + vi);
            }
        }
    }

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

复杂度： O(N × W × 平均组大小)。

循环顺序说明

正确——物品循环在容量循环内部：
  for w = W..0:
    尝试 A：dp[w] = max(dp[w], dp[w-2]+3)
    尝试 B：dp[w] = max(dp[w], dp[w-3]+5)
  → 每个容量下只从该组选最优的一件

错误——容量循环在物品循环内部：
  尝试 A：for w = W..0: dp[w] = max(dp[w], dp[w-2]+3)
  尝试 B：for w = W..0: dp[w] = max(dp[w], dp[w-3]+5)
  → A 和 B 可能都被选中，违反「每组最多一件」

6.2.7 多重背包

题目： N 种物品，每种有 cnt[i] 件（不是无限个）。在重量 W 内最大化总价值。

方法一：二进制拆分 — O(N log C × W)

核心思路： 0 到 cnt[i] 之间的任意数 k 都可以表示为 2 的幂次之和加余数。将 cnt[i] 件拆分为大小为 1, 2, 4, 8, ..., 余数的组，每组作为一件「超级物品」。

📄 C++ 完整代码

#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<pair<int,int>> items;

    for (int i = 0; i < n; i++) {
        int wi, vi, ci;
        cin >> wi >> vi >> ci;

        for (int k = 1; ci > 0; k *= 2) {
            int take = min(k, ci);
            items.push_back({take * wi, take * vi});
            ci -= take;
        }
    }

    // 对扩展后的物品做标准 0/1 背包
    vector<int> dp(W + 1, 0);
    for (auto [w, v] : items) {
        for (int cap = W; cap >= w; cap--)
            dp[cap] = max(dp[cap], dp[cap - w] + v);
    }

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

复杂度： O(Σ log(cnt[i]) × W) ≈ O(N log C × W)。

方法二：单调队列优化 — O(N × W)

对 cnt 很大（最大 10^6）的情况，二进制拆分仍然太慢。最优解使用单调队列。

核心思路： 按 w[i] 的余数对 DP 数组分组，在每个余数类内，转移变成一个滑动窗口最大值问题。

📄 C++ 完整代码

// 多重背包（单调队列优化）— O(N * W)
void bounded_knapsack_deque(vector<int>& dp, int wi, int vi, int ci, int W) {
    vector<int> prev = dp;
    for (int r = 0; r < wi; r++) {
        deque<int> dq;
        int max_k = (W - r) / wi;
        for (int k = 0; k <= max_k; k++) {
            int idx = r + k * wi;
            int val = prev[idx] - k * vi;
            while (!dq.empty() && dq.front() < k - ci) dq.pop_front();
            if (!dq.empty()) {
                int j = dq.front();
                dp[idx] = max(dp[idx], prev[r + j * wi] + (k - j) * vi);
            }
            while (!dq.empty() && prev[r + dq.back() * wi] - dq.back() * vi <= val)
                dq.pop_back();
            dq.push_back(k);
        }
    }
}

💡 何时用哪种方法：

cnt ≤ 1000，W ≤ 10^5 → 二进制拆分（实现更简单）

cnt 最大 10^6，W 最大 10^5 → 单调队列（只有 O(NW)）

6.2.8 完全背包——每种物品可选无限次

核心区别： 枚举顺序从「倒序」改为「正序」。

📄 C++ 完整代码

// 完全背包 — O(N × W)
// 正序枚举允许同一物品被多次选取
vector<int> unbounded_knapsack(int n, int W,
    vector<int>& wt, vector<int>& val) {
    vector<int> dp(W + 1, 0);
    for (int i = 0; i < n; i++) {
        for (int w = wt[i]; w <= W; w++) {   // ← 正序！
            dp[w] = max(dp[w], dp[w - wt[i]] + val[i]);
        }
    }
    return dp;
}

背包类型	每件可选次数	内层循环顺序
0/1 背包	最多 1 次	倒序（W → w[i]）
完全背包	无限次	正序（w[i] → W）
多重背包	最多 cnt[i] 次	拆分后按 0/1 处理

6.2.9 二维费用背包

物品同时有两种费用（如重量 + 体积），背包有两个限制。只需多一维状态。

📄 物品同时有两种费用（如重量 + 体积），背包有两个限制。只需多一维状态。

// 二维费用 0/1 背包 — O(N × V × M)
// 物品 i 有重量 w[i]、体积 v[i]、价值 c[i]
// 背包容量 V（重量）和 M（体积）
void two_dim_knapsack(int n, int V, int M,
    vector<int>& w, vector<int>& v, vector<int>& c) {
    vector<vector<int>> dp(V + 1, vector<int>(M + 1, 0));

    for (int i = 0; i < n; i++) {
        // 两个维度都倒序！保证 0/1 约束
        for (int j = V; j >= w[i]; j--) {
            for (int k = M; k >= v[i]; k--) {
                dp[j][k] = max(dp[j][k], dp[j - w[i]][k - v[i]] + c[i]);
            }
        }
    }
    // dp[V][M] 即为答案
}

⚠️ 关键： 两个维度都必须倒序枚举，否则同一物品会被多次计入。

6.2.10 背包方案数

将求最大值改为求满足条件的方案数：把 max 替换为累加，把初始值 dp[0] = 1 作为基础情况。

📄 将求最大值改为求**满足条件的方案数**：把 `max` 替换为累加，把初始值 `dp[0] = 1` 作为基础情况。

// 方案数背包：恰好装满 W 的方案数（对 MOD 取模）
// 物品无限次可选（完全背包版）
const int MOD = 1e9 + 7;

long long count_ways(int n, int W, vector<int>& wt) {
    vector<long long> dp(W + 1, 0);
    dp[0] = 1;  // 空背包：1 种方案（不选任何物品）

    for (int i = 0; i < n; i++) {
        for (int w = wt[i]; w <= W; w++) {   // 正序 = 完全背包
            dp[w] = (dp[w] + dp[w - wt[i]]) % MOD;
        }
    }
    return dp[W];
}

// 0/1 背包版：恰好装满的方案数
long long count_ways_01(int n, int W, vector<int>& wt) {
    vector<long long> dp(W + 1, 0);
    dp[0] = 1;

    for (int i = 0; i < n; i++) {
        for (int w = W; w >= wt[i]; w--)    // 倒序 = 0/1 背包
            dp[w] = (dp[w] + dp[w - wt[i]]) % MOD;
    }
    return dp[W];
}

典型应用：

「正好装满 W」的方案数 → 初始 dp[0]=1，dp[1..W]=0
「不超过 W」的方案数 → 初始全部为 1（任何子集都是合法方案）

6.2.11 背包问题决策对照表

需求	关键变化
求最大价值（0/1）	`dp[w] = max(dp[w], dp[w-wi]+vi)`，倒序
求最大价值（完全）	`dp[w] = max(dp[w], dp[w-wi]+vi)`，正序
求方案数（0/1）	`dp[w] += dp[w-wi]`，倒序，初始 `dp[0]=1`
求方案数（完全）	`dp[w] += dp[w-wi]`，正序，初始 `dp[0]=1`
求第 k 优解	每个状态存前 k 大的值，转移时用双指针合并
恰好装满	`dp[0]=1/0`，`dp[1..W]=-INF/0`
至多装满	`dp[0..W]` 全初始化为 0

⚠️ 第 6.2 章常见错误

LIS：严格递增用 upper_bound： 严格递增用 lower_bound；不减序列用 upper_bound。搞错会使 LIS 长度差 1。
0/1 背包：正向迭代重量： 正向迭代允许物品 i 被多次使用——那是无界背包，不是 0/1。0/1 背包始终倒序迭代。
网格路径：忘记处理堵塞格子： 若 grid[r][c] == '#'，设 dp[r][c] = 0（不是 dp[r-1][c] + dp[r][c-1]）。
网格路径计数中溢出： 路径数可能极大，用 long long 或模运算。
LIS：以为 tails 存储实际 LIS： 不是！tails 存储各长度子序列的最小可能尾元素。实际 LIS 需要单独重建。
分组背包：物品循环在容量外层： 物品循环必须在容量循环内部。若物品在外层，每件物品被当作独立的 0/1 物品处理，允许同组多件被选中。
多重背包二进制拆分后正向迭代： 拆分后超级物品仍是 0/1 约束——倒序迭代重量。正向迭代允许重用同一超级物品，结果错误。
二维背包只有一个维度倒序： 二维 0/1 背包中，重量和体积两个约束都需要其循环倒序迭代。

本章总结

📌 核心要点

问题	状态定义	递推	复杂度
LIS（O(N²)）	`dp[i]` = 以 A[i] 结尾的 LIS 长度	`dp[i]` = max(`dp[j]`+1)，j<i 且 A[j]<A[i]	`O(N²)`
LIS（O(N log N)）	tails[k] = 长度 k+1 的 IS 的最小尾部	二分查找 + 替换	`O(N log N)`
0/1 背包（一维）	`dp[w]` = 容量 ≤ w 时的最大价值	倒序迭代 w	`O(NW)`
无界背包	`dp[w]` = 容量 ≤ w 时的最大价值	正序迭代 w	`O(NW)`
分组背包	`dp[w]` = 最大价值，每组最多选 1 件	w 降序，物品循环在 w 循环内部	`O(N×W×组大小)`
多重背包	同 0/1	二进制拆分 → 0/1 背包	`O(N log C × W)`
网格路径	`dp[r][c]` = 到达 (r,c) 的路径数	`dp[r-1][c]` + `dp[r][c-1]`	`O(RC)`

❓ 常见问题

Q1：O(N log N) LIS 中 tails 数组存储的是实际 LIS 吗？

A：不是！ tails 存储的是「各长度递增子序列的最小尾元素」。其长度等于 LIS 长度，但元素本身可能不构成合法的递增子序列。要重建实际 LIS，需要记录每个元素的「前驱」。

Q2：0/1 背包为什么需要倒序迭代 w？

A：因为 dp[w] 需要上一件物品行的 dp[w - weight[i]]。正向迭代时，dp[w - weight[i]] 可能已被当前行（当前物品 i）更新，等于物品 i 被使用了多次。倒序迭代确保每件物品最多被使用一次。

Q3：无界背包（物品无限次可用）和 0/1 背包的代码只有什么区别？

A：只是内层循环方向。0/1 背包：w 从 W 降到 weight[i]（倒序）；无界背包：w 从 weight[i] 升到 W（正序）。

Q4：如果网格路径还可以向上或向左移动呢？

A：那么简单的网格 DP 就不再适用（因为会有环）。需要 BFS/DFS 或更复杂的 DP。标准网格路径 DP 只适用于「只向右/向下」的移动。

🔗 与后续章节的联系

第 3.3 章（排序与二分）：二分搜索是 O(N log N) LIS 的核心——对 tails 数组用 lower_bound
第 6.3 章（进阶 DP）：将背包扩展到状压 DP（物品集合 → 位掩码），将网格 DP 扩展到区间 DP
第 4.1 章（贪心）：区间调度问题有时可以转化为 LIS（通过 Dilworth 定理）
LIS 在 USACO Silver 中极为常见——二维 LIS、带权 LIS、LIS 计数变体频繁出现

练习题

题目 6.2.1 — LIS 长度 🟢 简单读取 N 个整数，找最长严格递增子序列的长度。

✅ 完整题解

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n; cin >> n;
    vector<int> a(n);
    for (int& x : a) cin >> x;

    vector<int> tails;
    for (int x : a) {
        auto it = lower_bound(tails.begin(), tails.end(), x);
        if (it == tails.end()) tails.push_back(x);
        else *it = x;
    }
    cout << tails.size() << "\n";
}

复杂度： O(N log N)。

题目 6.2.2 — LIS 计数 🔴 困难读取 N 个整数，找最长递增子序列的数量（对 10^9+7 取模）。

✅ 完整题解

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
int main() {
    int n; cin >> n;
    vector<int> a(n);
    for (int& x : a) cin >> x;

    vector<int> len(n, 1);
    vector<long long> cnt(n, 1);

    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (a[j] < a[i]) {
                if (len[j] + 1 > len[i]) {
                    len[i] = len[j] + 1;
                    cnt[i] = cnt[j];
                } else if (len[j] + 1 == len[i]) {
                    cnt[i] = (cnt[i] + cnt[j]) % MOD;
                }
            }
        }
    }

    int maxLen = *max_element(len.begin(), len.end());
    long long ans = 0;
    for (int i = 0; i < n; i++)
        if (len[i] == maxLen) ans = (ans + cnt[i]) % MOD;
    cout << ans << "\n";
}

复杂度： O(N²)。

题目 6.2.3 — 0/1 背包 🟡 中等 N 件物品，各有重量和价值，容量 W，找最大价值。（N, W ≤ 1000）

✅ 完整题解

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, W; cin >> n >> W;
    vector<int> wt(n), val(n);
    for (int i = 0; i < n; i++) cin >> wt[i] >> val[i];

    vector<int> dp(W + 1, 0);
    for (int i = 0; i < n; i++) {
        for (int w = W; w >= wt[i]; w--)  // 倒序：防止重复使用
            dp[w] = max(dp[w], dp[w - wt[i]] + val[i]);
    }
    cout << dp[W] << "\n";
}

复杂度： O(N × W)。

题目 6.2.4 — 收集星星 🟡 中等 N×M 网格有星星（'*'）和障碍（'#'），只能向右或向下从 (1,1) 移动到 (N,M)，最多能收集多少星星？

✅ 完整题解

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m; cin >> n >> m;
    vector<string> g(n);
    for (auto& row : g) cin >> row;

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

    dp[0][0] = (g[0][0] == '*') ? 1 : 0;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (i == 0 && j == 0) continue;
            if (g[i][j] == '#') continue;
            int star = (g[i][j] == '*') ? 1 : 0;
            int best = NEG;
            if (i > 0 && dp[i-1][j] != NEG) best = max(best, dp[i-1][j]);
            if (j > 0 && dp[i][j-1] != NEG) best = max(best, dp[i][j-1]);
            if (best != NEG) dp[i][j] = best + star;
        }
    }
    cout << max(0, dp[n-1][m-1]) << "\n";
}

复杂度： O(N × M)。

题目 6.2.5 — 恰好填满背包 🔴 困难背包变体：必须恰好用满容量 W（不是最多）。

✅ 完整题解

核心思路： 与标准 0/1 背包相同，但初始化 dp[w] = -INF（w > 0），只有 dp[0] = 0。只有从 dp[0]=0 可达的状态才有有限值。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, W; cin >> n >> W;
    vector<int> wt(n), val(n);
    for (int i = 0; i < n; i++) cin >> wt[i] >> val[i];

    const int NEG = -1e9;
    vector<int> dp(W + 1, NEG);
    dp[0] = 0;

    for (int i = 0; i < n; i++) {
        for (int w = W; w >= wt[i]; w--) {
            if (dp[w - wt[i]] != NEG)
                dp[w] = max(dp[w], dp[w - wt[i]] + val[i]);
        }
    }
    if (dp[W] == NEG) cout << "impossible\n";
    else cout << dp[W] << "\n";
}

复杂度： O(N × W)。

图示：LIS 耐心排序

LIS Patience Sort

上图用耐心排序类比展示 LIS。每「叠」表示一个潜在的子序列终点，叠的数量等于 LIS 长度。二分搜索以 O(log N) 找到每张牌的位置，总体 O(N log N) 算法。

图示：背包 DP 表

Knapsack DP Table

0/1 背包 DP 表：行 = 已考虑的物品，列 = 容量，每格展示可实现的最大价值。蓝色格子展示单件物品的贡献，绿色格子展示组合，带星号的格子是最优答案。

C++ 竞赛编程：USACO 学习指南