第五讲 · 动态规划原创

第五讲 · 动态规划 Banner

AcWing 算法基础课 Banner

第五讲 · 动态规划 Banner

AcWing 算法基础课 Banner

第五讲 · 动态规划 Banner

AcWing 算法基础课 Banner

"The art of programming is the art of organizing complexity." -- Edsger W. Dijkstra
本笔记为 第五讲 · 动态规划 的 C++ 模板与题解，内容涵盖线性 DP、背包问题、区间 DP、状态压缩 DP、树形 DP、计数 DP、数位 DP 以及记忆化搜索等算法竞赛中的核心动态规划模型。
动态规划 (Dynamic Programming, DP) 是算法竞赛的灵魂。它并非一种具体的算法，而是一种解决问题的思想——将一个复杂问题分解为更小的、重叠的子问题，并通过记录子问题的解来避免重复计算，最终构建出原问题的最优解。本章将带你深入探索 DP 的奥秘，从经典的背包问题到巧妙的状态压缩，掌握这门“用空间换时间”的艺术，将看似无从下手的问题化繁为简。[薰衣草紫]

🧠 第五讲 · 动态规划

🎒 1. 背包问题

IMPORTANT

摘要：背包问题（Knapsack Problem）是动态规划领域中最经典、最基础的模型。本文旨在构建一个关于背包问题的完整知识体系，从最基础的01背包开始，逐步深入到完全背包、多重背包和分组背包，并对相关的变种问题进行探讨。通过详细的思路剖析、状态转移方程推导、代码实现以及复杂度分析，本文希望能帮助读者彻底掌握背包问题的核心思想与解题技巧。

📜 1.1 背包问题概述

背包问题是动态规划的经典问题，核心是在容量限制下选择物品以达到某种最优值（如最大价值/最小重量）。通常有：

容量限制：背包总重量不超过 W
物品属性：每个物品有重量 w[i] 和价值 v[i]
目标：在不超过背包容量的前提下，最大化总价值

常见变种：

类型	特点
📦 01背包	每个物品最多选一次（选或不选）
♾️ 完全背包	每个物品可以选无限次
🔢 多重背包	每个物品有固定可选次数（如最多选`s[i]`次）
🧩 分组背包	物品被分为若干组，每组只能选一个物品

解决背包问题通常遵循以下四个步骤：

1、确定DP数组及下标含义

2、确定状态转移方程

3、DP数组初始化

4、确定遍历顺序

📦 1.2 01背包问题：每个物品最多选一次

🗂️ 1.2.0 洛谷 & 牛客题单

来源	题目/题单	说明
卡码网	46. 携带研究材料（第六期模拟笔试）	携带研究材料（第六期模拟笔试）
牛客	01背包_牛客题霸_牛客网	01背包
牛客	【模板】01背包_牛客题霸_牛客网	【模板】01背包
牛客竞赛	【模板】01背包	【模板】01背包
洛谷	https://www.luogu.com.cn/problem/U225269	U225269 01背包问题
洛谷	https://www.luogu.com.cn/training/680099	背包-01背包（题单）
洛谷	https://www.luogu.com.cn/training/28588	01背包（题单）
洛谷	https://www.luogu.com.cn/training/471524	01背包（题单）
洛谷	https://www.luogu.com.cn/training/764085	01背包问题（题单）

❓ 1.2.1 问题描述

有 N 件物品和一个容量为 V 的背包。第 i 件物品的体积是 v[i]，价值是 w[i]。每种物品只有一件，可以选择放入或不放入。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

🧊 1.2.2 二维解法：朴素思想

(1) 状态定义dp[i][j] 表示：从前 i 件物品中任意选择，放入容量为 j 的背包中所能获得的最大价值。

(2) 状态转移方程 对于第 i 件物品，我们面临两种选择：

不选：背包的价值与只考虑前 i-1 件物品时相同。此时 dp[i][j] = dp[i-1][j]。
选：前提是当前背包容量 j 必须大于等于物品 i 的体积 v[i]。价值为 dp[i-1][j-v[i]] + w[i]。

综合两种情况，取最大值： dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]] + w[i]);

即：

c++

dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]] + w[i])  // j ≥ v[i]
dp[i][j] = dp[i-1][j]                               // j < v[i]

(3) 代码实现

c++

#include <iostream>
using namespace std;
const int N = 1010;
int n, m;        // n: 物品数量, m: 背包容量
int v[N], w[N];  // v: 体积, w: 价值
int dp[N][N];    // dp[i][j]

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) { scanf("%d%d", &v[i], &w[i]); }
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= m; j++) {
      dp[i][j] = dp[i - 1][j];  // 默认不选第i个物品
      if (j >= v[i]) {          // 如果能装下，尝试选择
        dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);
      }
    }
  }

  printf("%d\n", dp[n][m]);
  return 0;
}

💡 1.2.3 一维解法：空间优化

观察到 dp[i][j] 的计算只依赖于 dp[i-1] 层的数据，因此可以优化空间。

(1) 状态定义。dp[j] 表示：容量为 j 的背包所能装下的最大价值。

(2) 状态转移方程

c++

dp[j] = max(dp[j], dp[j-v[i]] + w[i])

(3) 关键点：倒序遍历

IMPORTANT

为了确保计算 dp[j] 时所依赖的 dp[j-v[i]] 是上一轮（i-1）的状态，内层循环必须 从大到小（倒序） 遍历。如果正序遍历，dp[j-v[i]] 会被本轮更新，导致一个物品可能被重复选择，这就不再是01背包了。

(4) 代码实现

c++

#include <iostream>
using namespace std;

const int N = 1010;
int dp[N];
int v[N], w[N];

int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) { scanf("%d%d", &v[i], &w[i]); }
  for (int i = 1; i <= n; i++) {
    for (int j = m; j >= v[i]; j--) {  // 注意：倒序遍历
      dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
    }
  }
  cout << dp[m] << endl;
  return 0;
}

♾️ 1.3 完全背包问题：每个物品可选无限次

🗂️ 1.3.0 洛谷 & 牛客题单

来源	题目/题单	说明
牛客	完全背包_牛客题霸_牛客网	完全背包（核心代码模式）
牛客	【模板】完全背包_牛客题霸_牛客网	【模板】完全背包（ACM模式）
牛客	【模板】完全背包_牛客题霸_牛客网	【模板】完全背包（ACM模式）
牛客竞赛	【模板】完全背包	【模板】完全背包
洛谷	https://www.luogu.com.cn/problem/U200606	U200606 完全背包问题
洛谷	https://www.luogu.com.cn/problem/T164644	T164644 完全背包
洛谷	https://www.luogu.com.cn/problem/U401025	U401025 完全背包问题
洛谷	https://www.luogu.com.cn/problem/T181922	T181922 【例题】完全背包问题
洛谷	https://www.luogu.com.cn/problem/T633938	T633938 [C动态规划]完全背包问题
洛谷	https://www.luogu.com.cn/problem/T644462	T644462 【模板】完全背包问题
洛谷	https://www.luogu.com.cn/problem/T626650	T626650 完全背包问题
洛谷	https://www.luogu.com.cn/problem/U287919	U287919 完全背包问题
洛谷	https://www.luogu.com.cn/problem/U227266	U227266 完全背包问题
洛谷	https://www.luogu.com.cn/problem/T626648	T626648 完全背包问题
洛谷	https://www.luogu.com.cn/problem/U225366	U225366 完全背包问题
洛谷	https://www.luogu.com.cn/problem/U444165	U444165 完全背包问题
洛谷	https://www.luogu.com.cn/problem/T363712	T363712 完全背包问题
洛谷	https://www.luogu.com.cn/problem/T420343	T420343 【例题】完全背包问题
洛谷	https://www.luogu.com.cn/problem/T157476	T157476 完全背包问题
洛谷	https://www.luogu.com.cn/problem/U264941	U264941 完全背包问题
洛谷	https://www.luogu.com.cn/problem/U582594	U582594 完全背包问题
洛谷	https://www.luogu.com.cn/training/680112	背包-完全背包（题单）
洛谷	https://www.luogu.com.cn/training/453079	完全背包（题单）

❓ 1.3.1 问题描述

有 N 种物品和一个容量为 V 的背包，每种物品都有无限件可用。第 i 种物品的体积是 v[i]，价值是 w[i]。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

🧊 1.3.2 二维DP数组解法

(1) 状态定义dp[i][j]：前i个物品放入容量为j的背包中能获得的最大价值

(2) 状态转移方程 与01背包唯一的区别在于，每个物品可以被选择任意多次。这反映在状态转移方程上。

对于第 i 件物品，我们仍然面临两种选择：

不选：dp[i][j] = dp[i-1][j]。
选：可以选择1件、2件、...、k件。 dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]]+w[i], dp[i-1][j-2*v[i]]+2*w[i], ...)
这个方程太复杂了。我们可以换个角度： dp[i][j] 可以从 dp[i-1][j]（不选第i个）和 dp[i][j-v[i]]（选了至少一个第i个）转移而来。 dp[i][j-v[i]] 的含义是：在前 i 个物品中，放入容量 j-v[i] 背包的最大价值。在此基础上再选一个物品 i，价值就是 dp[i][j-v[i]] + w[i]。

最终的状态转移方程为：

c++

dp[i][j] = max(dp[i-1][j], dp[i][j-v[i]] + w[i])  // j ≥ v[i]
dp[i][j] = dp[i-1][j]                               // j < v[i]

(3) 代码实现

c++

#include <algorithm>
#include <iostream>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int dp[N][N];

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) { scanf("%d%d", &v[i], &w[i]); }
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= m; j++) {
      dp[i][j] = dp[i - 1][j];  // 不选第i个物品
      if (j >= v[i]) {
        // 选第i个物品，注意这里是 dp[i][...] 而不是 dp[i-1][...]
        dp[i][j] = max(dp[i][j], dp[i][j - v[i]] + w[i]);
      }
    }
  }

  printf("%d\n", dp[n][m]);
  return 0;
}

💡 1.3.3 一维解法与遍历顺序

(1) 状态定义。dp[j] 表示：容量为 j 的背包所能装下的最大价值。

(2) 状态转移方程 将二维方程 dp[i][j] = max(dp[i-1][j], dp[i][j-v[i]] + w[i]) 转化为一维，去掉第一维 i 后，变为 dp[j] = max(dp[j], dp[j - v[i]] + w[i])。方程形式与01背包相同，但实现细节不同。

(3) 关键点：正序遍历

IMPORTANT

为了让每个物品可以被重复选择，实现 dp[i][j-v[i]] 的效果，即在当前轮次 i 中，物品 i 可以被重复选择，我们需要使用本轮更新过的 dp 值。因此，内层循环必须 从小到大（正序） 遍历。

(4) 代码实现

c++

#include <iostream>
using namespace std;

const int N = 1010;
int dp[N];
int v[N], w[N];

int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) { scanf("%d%d", &v[i], &w[i]); }
  for (int i = 1; i <= n; i++) {
    for (int j = v[i]; j <= m; j++) {  // 注意：正序遍历
      dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
    }
  }
  cout << dp[m] << endl;
  return 0;
}

🔢 1.4 多重背包问题：每个物品有数量上限

🗂️ 1.4.0 洛谷 & 牛客题单

来源	题目/题单	说明
牛客	【模板】多重背包_牛客题霸_牛客网	【模板】多重背包
朴素写法⬇️	朴素写法⬇️	朴素写法⬇️
洛谷	https://www.luogu.com.cn/problem/U296062	U296062 多重背包板子
洛谷	https://www.luogu.com.cn/problem/T634681	T634681 [C动态规划]多重背包
洛谷	https://www.luogu.com.cn/problem/U280382	U280382 多重背包问题
洛谷	https://www.luogu.com.cn/problem/T506338	T506338 多重背包【背包】
洛谷	https://www.luogu.com.cn/problem/T546409	T546409 【模板】多重背包问题（弱化版）
洛谷	https://www.luogu.com.cn/problem/U421512	U421512 【模板】多重背包问题（弱化版）
洛谷	https://www.luogu.com.cn/problem/T182351	T182351 【例题】多重背包问题
洛谷	https://www.luogu.com.cn/problem/U120987	U120987 偷东西(多重背包)
洛谷	https://www.luogu.com.cn/problem/T127078	T127078 庆功会(多重背包)
洛谷	https://www.luogu.com.cn/problem/T170583	T170583 【背包】【模板】多重背包-1
洛谷	https://www.luogu.com.cn/problem/T627121	T627121 少量多重背包

二进制优化⬇️	二进制优化⬇️	二进制优化⬇️
洛谷	https://www.luogu.com.cn/problem/T627123	T627123 多重背包
洛谷	https://www.luogu.com.cn/problem/T473627	T473627 多重背包（2）
洛谷	https://www.luogu.com.cn/problem/U536214	U536214 多重背包问题Ⅱ
洛谷	https://www.luogu.com.cn/problem/U296083	U296083 多重背包二进制优化
洛谷	https://www.luogu.com.cn/problem/U410562	U410562 多重背包
洛谷	https://www.luogu.com.cn/problem/U421513	U421513 【模板】多重背包问题（强化版）

单调队列优化⬇️	单调队列优化⬇️	单调队列优化⬇️
洛谷	https://www.luogu.com.cn/problem/U421515	U421515 【模板】多重背包问题（终极版）
洛谷	https://www.luogu.com.cn/problem/U312099	U312099 多重背包单调队列优化
洛谷	https://www.luogu.com.cn/problem/U296086	U296086 多重背包单调队列优化
洛谷	https://www.luogu.com.cn/problem/T343317	T343317 多重背包
洛谷	https://www.luogu.com.cn/problem/T362036	T362036 【模板】多重背包问题
洛谷	https://www.luogu.com.cn/problem/T318392	T318392 0x59-单调队列优化dp-多重背包
洛谷	https://www.luogu.com.cn/problem/T318628	T318628 【模板】多重背包
洛谷	https://www.luogu.com.cn/problem/T557386	T557386 【模板】多重背包问题（强化版）/ 2025跨年祭单题
洛谷	https://www.luogu.com.cn/problem/U410504	U410504 【模板】完全背包（加强版）
洛谷	https://www.luogu.com.cn/problem/T527363	T527363 多重背包

❓ 1.4.1 问题描述

有 N 种物品和一个容量为 V 的背包。第 i 种物品最多有 s[i] 件，每件体积是 v[i]，价值是 w[i]。求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。

🐌 1.4.2 朴素解法：转化为01背包

最直接的思路是，将第 i 种物品（共 s[i] 件）看作 s[i] 件完全相同的、但独立的物品，然后直接应用01背包求解。

WARNING

缺点：当 s[i] 很大时，物品总数 Σs[i] 会非常大，导致超时。时间复杂度为

$O (V * \sum s [i])$ 。

(1) 状态转移方程

c++

dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i] * k] + w[i] * k); // 0 <= k <= s[i]

(2) 核心代码

c++

  for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= m; j++) {
      // 枚举第i个物品选k件
      for (int k = 0; k <= s[i] && k * v[i] <= j; k++) {
        dp[i][j] = max(dp[i][j], dp[i - 1][j - k * v[i]] + k * w[i]);
      }
    }
  }

(3) 完整代码 (二维)

c++

#include <algorithm>
#include <iostream>
using namespace std;
const int N = 110;
int n, m;
int v[N], w[N], s[N];
int dp[N][N];  // 使用二维DP演示

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) { scanf("%d%d%d", &v[i], &w[i], &s[i]); }

  for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= m; j++) {
      // 枚举第i个物品选k件
      for (int k = 0; k <= s[i] && k * v[i] <= j; k++) {
        dp[i][j] = max(dp[i][j], dp[i - 1][j - k * v[i]] + k * w[i]);
      }
    }
  }

  printf("%d\n", dp[n][m]);
  return 0;
}

(4) 完整代码 (一维)

c++

#include <algorithm>
#include <iostream>
using namespace std;
const int N = 110;
int n, m;
int v[N], w[N], s[N];
int dp[N];  // 使用一维DP演示

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) { scanf("%d%d%d", &v[i], &w[i], &s[i]); }

  for (int i = 1; i <= n; i++) {
    for (int j = m; j >= 0; j--) {
      // 枚举第i个物品选k件
      for (int k = 0; k <= s[i] && k * v[i] <= j; k++) {
        dp[j] = max(dp[j], dp[j - k * v[i]] + k * w[i]);
      }
    }
  }

  printf("%d\n", dp[m]);
  return 0;
}

🚀 1.4.3 二进制优化：高效拆分

(1) 思路

NOTE

朴素解法的问题在于对 k 的枚举是线性的。我们可以用二进制思想来优化。任何一个整数 s 都可以被拆分为 1, 2, 4, ..., 2^p 以及一个余数 r 的和。通过这些拆分出的数字的组合，可以凑出 1 到 s 之间的任何整数。

我们可以将 s[i] 件物品打包成 log(s[i]) 个新的物品。例如，s[i]=10，我们可以打包成4组：

1件物品 i，体积 1*v[i]，价值 1*w[i]
2件物品 i，体积 2*v[i]，价值 2*w[i]
4件物品 i，体积 4*v[i]，价值 4*w[i]
3件物品 i (余下的 10-1-2-4=3)，体积 3*v[i]，价值 3*w[i]

对这些新打包出的物品做一遍01背包即可。时间复杂度： $O (V * \sum l o g (s [i]))$ ，效率大大提高。

(2) 完整代码实现

c++

#include <algorithm>
#include <cstdio>
#include <iostream>
using namespace std;
const int N = 12010;  // n*log(s)
const int M = 2010;
int cnt = 0;  // 每种物品拆分后，一共形成的组数，最后就是01背包问题
int v[N], w[N];
int n, m;
int dp[M];  //  01背包的一维优化

int main() {
  scanf("%d%d", &n, &m);

  for (int i = 1; i <= n; i++) {
    int vx, wx, s;
    scanf("%d%d%d", &vx, &wx, &s);
    int k = 1;
    while (k <= s) {  // 这里是 k <= s
      cnt++;          // 总组数+1
      v[cnt] = vx * k;
      w[cnt] = wx * k;

      s -= k;
      k *= 2;
    }
    // 如果s按照 1 2 4 8 …… 拆分后还剩下，就直接加入到里面
    if (s > 0) {
      cnt++;  // 总组数+1
      v[cnt] = vx * s;
      w[cnt] = wx * s;
    }
  }
  n = cnt;  // 拆分后相当于现在有cnt个物品了，然后决定每个物品选还是不选

  // 把所有的物品都拆分了，放入到了v[],
  // w[]中，下面就可以用01背包来遍历实现最大值了
  for (int i = 1; i <= n; i++) {
    for (int j = m; j >= v[i]; j--) { dp[j] = max(dp[j], dp[j - v[i]] + w[i]); }
  }

  printf("%d\n", dp[m]);
  return 0;
}

🚄 1.4.4 单调队列优化：终极方案

这是一种更高级的优化技巧，可以将时间复杂度降至 O(NV)，但实现较为复杂，这里不做详细展开。其核心思想是利用单调队列来优化对 k 的决策过程。

🧩 1.5 分组背包问题：每组物品择一而从

🗂️ 1.5.0 洛谷 & 牛客题单

来源	题目/题单	说明
牛客	【模板】分组背包_牛客题霸_牛客网	【模板】分组背包
洛谷	https://www.luogu.com.cn/problem/T506343	T506343 分组背包【背包】
洛谷	https://www.luogu.com.cn/problem/U115691	U115691 分组背包
洛谷	https://www.luogu.com.cn/problem/T616740	T616740 通天之分组背包
洛谷	https://www.luogu.com.cn/problem/U603366	U603366 分组背包
洛谷	https://www.luogu.com.cn/problem/T519115	T519115 通天之分组背包
洛谷	https://www.luogu.com.cn/problem/U560163	U560163 【模板】分组背包
洛谷	https://www.luogu.com.cn/problem/U280369	U280369 分组背包问题
洛谷	https://www.luogu.com.cn/problem/T570467	T570467 通天之分组背包
洛谷	https://www.luogu.com.cn/problem/U517864	U517864 分组背包
洛谷	https://www.luogu.com.cn/problem/U536284	U536284 分组背包问题
洛谷	https://www.luogu.com.cn/problem/P1757	P1757 通天之分组背包

❓ 1.5.1 问题描述

有 N 组物品和一个容量为 V 的背包。第 i 组有 s[i] 件物品。同一组内的物品最多只能选一个。每件物品的体积是 v[i][j]，价值是 w[i][j]。求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。简要来说：

物品被分为若干组
每组物品中至多选择一件
求最大价值

⚙️ 1.5.2 状态转移与实现

(1) 思路 分组背包的思路是：对于每一组物品，我们有几种决策：

不选该组的任何物品。
选择该组的第1件物品。
选择该组的第2件物品。
...

这本质上是将一组内的多个物品视为一个整体决策。

(2) 状态转移方程 其中 i 代表组号，k 代表组内物品编号。

c++

dp[j] = max(dp[j], dp[j - v[i][k]] + w[i][k])

(3) 代码实现 代码结构是三层循环：

最外层：遍历每一个分组。
中间层：倒序遍历背包容量 j（因为每组最多选一个，本质上是01背包）。
最内层：遍历当前分组内的所有物品，进行决策。

c++

#include <algorithm>
#include <cstdio>
#include <iostream>
using namespace std;
const int N = 110;
int n, m;
int v[N][N], w[N][N];  // v[i][j] 表示第i组第j个物品
int s[N];
int f[N];  // f[j] 表示容量为j的情况下的最大值

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &s[i]);
    for (int j = 1; j <= s[i]; j++) { scanf("%d%d", &v[i][j], &w[i][j]); }
  }

  for (int i = 1; i <= n; i++)           // 循环分组
    for (int j = m; j >= 0; j--) {       // 注意体积从大到小枚举！！01背包
      for (int k = 1; k <= s[i]; k++) {  // 每个分组内部选择第k个物品
        if (j >= v[i][k]) f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
      }
    }
  cout << f[m];
  return 0;
}

✨ 1.6 背包问题变种

🔢 1.6.1 求方案总数

问题：求恰好装满背包的方案数。
状态转移：dp[j] += dp[j - v[i]]
初始化：dp[0] = 1（表示容量为0的背包有一种方案，即什么都不装），其余为0。

📝 1.6.2 求具体方案

需要记录下状态是如何转移过来的。
一种方法是开一个额外的数组 path[i][j]，记录在状态 dp[i][j] 时是否选择了物品 i。
另一种方法是，在计算完 dp 数组后，从 dp[n][m] 开始，根据状态转移方程逆向推导出选择路径。

⚖️ 1.6.3 二维费用背包

问题：每件物品有两个属性，如体积和重量。背包也有对应的两种容量限制。
状态定义：dp[j][k] 表示体积为 j、重量为 k 的背包能获得的最大价值。
状态转移：dp[j][k] = max(dp[j][k], dp[j - v[i]][k - c[i]] + w[i])

📊 1.7 总结

🎯 1.7.1 核心区别

01背包 vs 完全背包：核心区别在于物品是否可以重复选取，这直接体现在一维优化时内层循环的遍历顺序上（倒序 vs 正序）。
多重背包：是01背包的扩展，通过二进制优化可以高效地转化为01背包问题。
分组背包：决策单位从单个物品变成了“一组物品”，每组内的物品是互斥的。

📈 1.7.2 四大背包模型核心对比

步骤 \ 模型	01背包	完全背包	多重背包	分组背包
核心约束	每件物品最多选一次	每种物品可选无限次	每种物品最多选`s[i]`次	每组物品最多选一个
核心思想	对每个物品决策“选”或“不选”	对每个物品决策“选0,1,2...次”	转化为01背包问题	组间进行01决策，组内进行多选一决策
一维DP数组含义	`dp[j]` 表示容量 `j` 的最大价值	同左	同左	同左
一维递推公式	`dp[j] = max(dp[j], dp[j-v[i]]+w[i])`	`dp[j] = max(dp[j], dp[j-v[i]]+w[i])`	`dp[j] = max(dp[j], dp[j-v_new]+w_new)`	`dp[j] = max(dp[j], dp[j-v[i][k]]+w[i][k])`
遍历顺序关键	先物品，后背包（倒序）	先物品，后背包（正序）	先对物品二进制拆分，再按01背包处理	先分组，后背包（倒序），再遍历组内物品

🔄 1.7.3 遍历顺序深度剖析

对于0-1背包和完全背包问题：

(1) 0-1背包

二维dp[i][j]数组，i表示物品，j表示背包

遍历顺序	顺序+顺序	顺序+倒序	倒序+顺序	倒序+倒序
先遍历物品，再遍历背包	✅	✅	❌	❌
先遍历背包，再遍历物品	✅	❌	❌	❌

一维dp[j]数组,j表示背包

遍历顺序	顺序+顺序	顺序+倒序	倒序+顺序	倒序+倒序
先遍历物品，再遍历背包	❌（完全背包）	✅	❌	❌
先遍历背包，再遍历物品	❌	❌	❌	❌

(2) 完全背包

二维dp[i][j]数组，i表示物品，j表示背包

遍历顺序	顺序+顺序	顺序+倒序	倒序+顺序	倒序+倒序
先遍历物品，再遍历背包	✅	❌	❌	❌
先遍历背包，再遍历物品	✅	❌	❌	❌

一维dp[j]数组,j表示背包

遍历顺序	顺序+顺序	顺序+倒序	倒序+顺序	倒序+倒序
先遍历物品，再遍历背包	✅	❌	✅	❌
先遍历背包，再遍历物品	✅	✅	❌	❌

⭐ 1.7.4 遍历顺序总结

问题模型	核心约束	一维DP核心遍历顺序	关键原因
📦 01背包	每件物品最多选一次	先物品，后倒序背包	防止物品被重复选取
♾️ 完全背包	每种物品可选无限次	先物品，后正序背包	允许物品被重复选取
🔢 多重背包	每种物品最多选`s[i]`次	(拆分后) 按01背包顺序	转化为01背包问题处理
🧩 分组背包	每组物品最多选一个	先分组，后倒序背包	组间决策为01背包逻辑
方案数(组合)	顺序无关 `(1,2)`=`(2,1)`	先物品，后背包	物品的添加顺序不影响结果
方案数(排列)	顺序相关 `(1,2)`≠`(2,1)`	先背包，后物品	物品的添加顺序会产生新结果

📏 2. 线性DP

📐 2.1 数字三角形

🔗 练习平台

来源	题目/题单	说明
leetcode	120. 三角形最小路径和 - 力扣（LeetCode）	120. 三角形最小路径和
洛谷	https://www.luogu.com.cn/problem/P1216	P1216 [IOI 1994 / USACO1.5] 数字三角形 Number Triangles
洛谷	https://www.luogu.com.cn/problem/T559613	T559613 数字三角形 Number Triangles
洛谷	https://www.luogu.com.cn/problem/U279551	U279551 数字三角形
洛谷	https://www.luogu.com.cn/problem/U465517	U465517 数字三角形（数塔问题）
洛谷	https://www.luogu.com.cn/problem/U444125	U444125 数塔问题（IOI1994）
洛谷	https://www.luogu.com.cn/problem/U218133	U218133 数塔问题
洛谷	https://www.luogu.com.cn/problem/U510104	U510104 数塔问题
洛谷	https://www.luogu.com.cn/problem/U508379	U508379 【基础】数塔问题
洛谷	https://www.luogu.com.cn/problem/T569741	T569741 数塔
洛谷	https://www.luogu.com.cn/problem/U474202	U474202 数塔问题
洛谷	https://www.luogu.com.cn/problem/U113807	U113807 数塔（升级版）（难）

🔗题目和代码实现

给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。
  7
3   8
8   1   0
2   7   4   4
4   5   2   6   5
1
2
3
4
5
输入格式：
第一行包含整数 n，表示数字三角形的层数。
接下来 n 行，每行包含若干整数，其中第 i 行表示数字三角形第 i 层包含的整数。
输出格式
输出一个整数，表示最大的路径数字和。
输入样例：
5
7
3 8
8 1 0 
2 7 4 4
4 5 2 6 5
1
2
3
4
5
6
输出样例：
30
1

代码实现

c++

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N = 510;
const int INF = 1e9;
int a[N][N], f[N][N];

int main()
{
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) 
        for(int j = 1; j <= i; j++) 
            scanf("%d", &a[i][j]);
    
    // 初始化，防止边界问题
    for(int i = 0; i <= n; i++)
        for(int j = 0; j <= i + 1; j++) 
            f[i][j] = -INF;
    
    // DP开始
    f[1][1] = a[1][1];
    // 从上往下递推
    for(int i = 2; i <= n; i++) 
        for(int j = 1; j <= i; j++) 
        {
            f[i][j] = max(f[i-1][j-1], f[i-1][j]) + a[i][j];
        }
    
    // 找出最后一行的最大值
    int res = -INF;
    for(int i = 1; i <= n; i++) res = max(res, f[n][i]);
    
    printf("%d\n", res);
    return 0;
}

📈 2.2 最长上升子序列 (LIS)

📎2.2.0 练习链接

来源	题目/题单	说明
leetcode	300. 最长递增子序列 - 力扣（LeetCode）	300. 最长递增子序列
时间复杂度： $O (n^{2})$ 解法	时间复杂度： $O (n^{2})$ 解法	时间复杂度： $O (n^{2})$ 解法
牛客	最长上升子序列(一)_牛客题霸_牛客网	最长上升子序列(一)
牛客	最长递增子序列（LCS）_牛客题霸_牛客网	最长递增子序列（LCS）
洛谷	https://www.luogu.com.cn/problem/B3637	B3637 最长上升子序列
洛谷	https://www.luogu.com.cn/problem/T404362	T404362 c++-中高-3：最长递增子序列
洛谷	https://www.luogu.com.cn/problem/U255571	U255571 最长上升子序列（基础版）
时间复杂度： $O (n l o g n)$ 解法	时间复杂度： $O (n l o g n)$ 解法	时间复杂度： $O (n l o g n)$ 解法
牛客	最长上升子序列(二)_牛客题霸_牛客网	最长上升子序列(二)
洛谷	https://www.luogu.com.cn/problem/U255583	U255583 最长上升子序列（加强版）
洛谷	https://www.luogu.com.cn/problem/T562238	T562238 最长上升子序列【数据增强版】
变种/综合	变种/综合	变种/综合
牛客	最长递增子序列_牛客题霸_牛客网	最长递增子序列
洛谷	https://www.luogu.com.cn/problem/U195944	U195944 最长上升子序列（加强）
洛谷	https://www.luogu.com.cn/problem/T663805	T663805 最长递增子序列的个数
洛谷	https://www.luogu.com.cn/problem/T357466	T357466 最长上升子序列 - 最长递增子序列 V2
洛谷	https://www.luogu.com.cn/training/348162	1.2最长上升子序列模型（题单）
洛谷	https://www.luogu.com.cn/training/448307	子序列/子段相关的动态规划（题单）

❓ 2.2.1 问题描述

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例：
输入：nums = [10,9,2,5,3,7,101,18]
输出：4 (最长递增子序列是 [2,3,7,101])

🐌 2.2.2 朴素版：动态规划

时间复杂度： $O (n^{2})$

（1）状态定义：dp[i] 表示 以 nums[i] 结尾 的最长递增子序列的长度。

为什么必须“以 nums[i] 结尾”？

因为只有固定结尾元素，才能确保递增性比较（nums[j] < nums[i]）是有意义的。

（2）状态转移方程：

对每个位置 i，遍历 j ∈ [0, i-1]：

if n u m s [i] > n u m s [j] \Rightarrow d p [i] = max (d p [i], d p [j] + 1)

（3）dp[i]的初始化

每个元素 nums[i] 最短的递增子序列就是它自己，因此初始：

d p [i] = 1

最终答案：

LIS = max (d p [0], d p [1], \dots, d p [n - 1])

（4）遍历顺序：

dp[i] 是有0到i-1各个位置的最长递增子序列推导而来，那么遍历i一定是从前向后遍历。

j其实就是遍历0到i-1，那么是从前到后，还是从后到前遍历都无所谓，只要把 0 到 i-1 的元素都遍历了就行了。所以默认习惯从前向后遍历。

(5) 代码实现

c++

#include <iostream>
using namespace std;
const int N = 5e3 + 5;
int nums[N], dp[N];
int main() {
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; i++) { scanf("%d", nums + i); }
  // 初始化
  fill(dp, dp + N, 1);
  int res = 1;
  // 动态规划
  for (int i = 1; i < n; i++) {
    for (int j = 0; j < i; j++) {
      if (nums[j] < nums[i] && dp[i] < dp[j] + 1) { dp[i] = dp[j] + 1; }
    }
    res = max(res, dp[i]);
  }
  printf("%d", res);
  return 0;
}

⚡ 2.2.3 优化版：二分法 + 贪心

时间复杂度： $O (n \log n)$

（1）优化思路

朴素版需要两重循环（O(n²)），我们可以用 贪心 + 二分 优化。

（2）思路核心

NOTE

维护一个数组 tails：

tails[k] 表示 长度为 k+1 的所有递增子序列中 的最小结尾元素。
tails 数组本身是 单调递增 的。

每遇到新元素 x：

若 x 比 tails 中所有元素都大，直接加到 tails 后面，LIS 长度+1。
否则，在 tails 中找到第一个大于等于 x 的元素，并用 x 替换它。这表示我们找到了一个结尾更小的、同样长度的递增子序列，这为后续构造更长的序列提供了更多可能性（贪心）。

最终 tails 的长度就是 LIS 的长度。

（3）举例分析

nums = [10,9,2,5,3,7,101,18]

nums[i]	操作说明	tails数组	长度
10	tails = [10]	[10]	1
9	9替换10	[9]	1
2	2替换9	[2]	1
5	5>2 → 添加	[2,5]	2
3	3替换5	[2,3]	2
7	7>3 → 添加	[2,3,7]	3
101	101>7 → 添加	[2,3,7,101]	4
18	18替换101	[2,3,7,18]	4

最终长度 = 4 ✅

（4）代码实现

c++

#include <cstdio>
#include <iostream>
using namespace std;
/*
  功能：求一个序列的最长严格递增子序列（LIS）的长度
  算法：贪心 + 二分（O(n log n)）
*/
const int N = 1e5 + 5;
int a[N], tails[N];
int main() {
  int n;
  scanf("%d", &n);
  // 输入数组
  for (int i = 0; i < n; i++) { scanf("%d", &a[i]); }
  // 初始化
  int len = 1;      // 当前最长递增子序列长度
  tails[0] = a[0];  // tails[i] 表示长度为 i+1 的递增子序列的末尾最小值

  for (int i = 1; i < n; i++) {
    // 如果当前数比 tails[len-1] 还大，说明可以直接扩展LIS
    if (a[i] > tails[len - 1]) {
      tails[len++] = a[i];
    } else {
      // 否则，用二分查找“第一个 >= a[i]”的tails位置替换
      int l = 0, r = len - 1;
      while (l < r) {
        int mid = l + (r - l) / 2;
        if (tails[mid] >= a[i])
          r = mid;
        else
          l = mid + 1;
      }
      tails[l] = a[i];  // 更新该位置的最小值
    }
  }
  printf("%d\n", len);
  return 0;
}

📊 2.2.4 对比总结

解法	时间复杂度	空间复杂度	思路特点	适用场景
DP O(n²)	O(n²)	O(n)	简单易理解，直接比较	n ≤ 5e3
贪心 + 二分	O(n log n)	O(n)	高效，利用tails记录最优解	n ≤ 1e5

🔗 2.3 最长公共子序列

🔗练习链接

来源	题目/题单	说明
leetcode	718. 最长重复子数组 - 力扣（LeetCode）	718. 最长重复子数组
牛客	最大公共子串_牛客题霸_牛客网	最大公共子串（ACM模式）
牛客	最长公共子串_牛客题霸_牛客网	最长公共子串（核心代码模式）
洛谷	https://www.luogu.com.cn/problem/T493246	T493246 最长公共子串
洛谷	https://www.luogu.com.cn/problem/U396793	U396793 最长公共子串

🔗题目和代码实现

问题描述 给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。若没有公共子序列，则返回 0。
示例：
输入：text1 = "abcde", text2 = "ace"
输出：3 (最长公共子序列是 "ace")

(1) 状态定义dp[i][j]：字符串 text1 的前 i 个字符 (text1[0...i-1]) 与 text2 的前 j 个字符 (text2[0...j-1]) 的最长公共子序列长度。

(2) 状态转移方程

如果 text1[i-1] == text2[j-1]，说明找到了一个公共字符。 dp[i][j] = dp[i-1][j-1] + 1
如果 text1[i-1] != text2[j-1]，则LCS来自以下两者中的较大者：
- text1 的前 i-1 个字符与 text2 的前 j 个字符的LCS
- text1 的前 i 个字符与 text2 的前 j-1 个字符的LCS dp[i][j] = max(dp[i-1][j], dp[i][j-1])

(3) 初始化dp[0][j] = 0 和 dp[i][0] = 0，因为任何字符串与空串的LCS长度都是0。

(4) 完整代码

c++

// 假设 f[N][N] 已定义，A 和 B 字符串从下标1开始
for(int i = 1; i <= n; i++) {
    for(int j = 1; j <= m; j++) {
        if (A[i] == B[j]) {
            f[i][j] = f[i-1][j-1] + 1;
        } else {
            f[i][j] = max(f[i-1][j], f[i][j-1]);
        }
    }
}
cout << f[n][m];

✂️ 2.4 编辑距离

🔗练习链接

来源	题目/题单	说明
leetcode	392. 判断子序列 - 力扣（LeetCode）	392. 判断子序列
牛客	判断子序列_牛客题霸_牛客网	判断子序列

leetcode	583. 两个字符串的删除操作 - 力扣（LeetCode）	583. 两个字符串的删除操作

leetcode	72. 编辑距离 - 力扣（LeetCode）	72. 编辑距离
牛客	计算字符串的编辑距离_牛客题霸_牛客网	计算字符串的编辑距离
牛客	最短编辑距离_牛客题霸_牛客网	最短编辑距离
牛客	编辑距离(一)_牛客题霸_牛客网	编辑距离(一)
牛客	编辑距离(二)_牛客题霸_牛客网	编辑距离(二)
洛谷	https://www.luogu.com.cn/problem/P2758	P2758 编辑距离
洛谷	https://www.luogu.com.cn/problem/U566633	U566633 字符串编辑距离
洛谷	https://www.luogu.com.cn/problem/U279553	U279553 最短编辑距离
洛谷	https://www.luogu.com.cn/problem/T633971	T633971 编辑距离
洛谷	https://www.luogu.com.cn/problem/T560846	T560846 【7-1例题B】编辑距离
洛谷	https://www.luogu.com.cn/problem/U627380	U627380 字符串编辑距离
洛谷	https://www.luogu.com.cn/problem/T663529	T663529 编辑距离
洛谷	https://www.luogu.com.cn/problem/U212825	U212825 编辑距离（动态规划）
洛谷	https://www.luogu.com.cn/problem/T513164	T513164 编辑距离

🔗题目和代码实现

P2758 编辑距离：https://www.luogu.com.cn/problem/P2758
问题描述 设 A 和 B 是两个字符串。我们要用最少的字符操作次数，将字符串 A 转换为字符串 B。操作共三种：
删除一个字符；
插入一个字符；
将一个字符改为另一个字符。
示例：
输入：A = "sfdqxbw", B = "gfdgw"
输出：4

(1) 状态定义dp[i][j] 表示：将字符串 A 的前 i 个字符转换成 B 的前 j 个字符所需的最少操作数。

(2) 状态转移方程

如果 A[i-1] == B[j-1]，最后一个字符相同，无需操作。 dp[i][j] = dp[i-1][j-1]
如果 A[i-1] != B[j-1]，考虑三种操作：
- 替换 A[i-1]： dp[i-1][j-1] + 1
- 删除 A[i-1]： dp[i-1][j] + 1
- 插入一个字符到 A 末尾以匹配 B[j-1]： dp[i][j-1] + 1

所以：

c++

dp[i][j] = min({dp[i-1][j-1], dp[i-1][j], dp[i][j-1]}) + 1

(3) 初始化

dp[0][0] = 0，两个空串之间不需要任何操作。

dp[i][0] = i，将长度为 i 的 word1 转成空串，需要删除 i 次。

dp[0][j] = j，将空串转成长度为 j 的 word2，需要插入 j 次。

代码示例：

c++

for (int i = 1; i <= m; i++) dp[i][0] = i;
for (int j = 1; j <= n; j++) dp[0][j] = j;

(4) 完整代码

c++

#include <iostream>
using namespace std;

const int N = 2e3 + 5;
int dp[N][N];

int main() {
  string s1, s2;
  cin >> s1 >> s2;

  int m = s1.length(), n = s2.length();

  // 初始化
  for (int i = 1; i <= m; i++) dp[i][0] = i;
  for (int j = 1; j <= n; j++) dp[0][j] = j;

  // 状态转移
  for (int i = 1; i <= m; i++) {
    for (int j = 1; j <= n; j++) {
      if (s1[i - 1] == s2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1];
      } else {
        dp[i][j] = min(
            dp[i - 1][j] + 1,                      // 删除
            min(dp[i][j - 1] + 1, dp[i - 1][j - 1] + 1) // 插入 / 替换
        );
      }
    }
  }

  printf("%d", dp[m][n]);
  return 0;
}

（5）时间与空间复杂度

时间复杂度：O(n * m)，空间复杂度：O(n * m)（可优化为 O(min(n, m))）

（6）小结

操作类型	含义	对应转移
插入	在 word1 末尾插入一个字符	`dp[i][j - 1] + 1`
删除	删除 word1 的最后一个字符	`dp[i - 1][j] + 1`
替换	将 word1 的最后一个字符改成 word2 的	`dp[i - 1][j - 1] + 1`

↔️ 3. 区间DP

🗂️ 3.0 洛谷 & 牛客题单

来源	题目/题单	说明
牛客	【模板】区间dp_牛客题霸_牛客网	【模板】区间dp
牛客竞赛	石子合并	石子合并
洛谷	https://www.luogu.com.cn/problem/P1775	P1775 石子合并（弱化版）
洛谷	https://www.luogu.com.cn/problem/T113701	T113701 石子合并（简单版）
洛谷	https://www.luogu.com.cn/problem/T571370	T571370 石子合并（弱化版）
洛谷	https://www.luogu.com.cn/problem/U461930	U461930 石子合并
洛谷	https://www.luogu.com.cn/problem/U97736	U97736 石子合并（线性）
进阶⬇️	进阶⬇️	进阶⬇️
洛谷	https://www.luogu.com.cn/problem/P1880	P1880 [NOI1995] 石子合并（环形DP问题）
洛谷	https://www.luogu.com.cn/problem/U322569	U322569 大石子合并（环形DP问题）
洛谷	https://www.luogu.com.cn/problem/T376874	T376874 石子合并（环形DP问题）
洛谷	https://www.luogu.com.cn/problem/T571371	T571371 [NOI1995] 石子合并（环形DP问题）
洛谷	https://www.luogu.com.cn/problem/P5569	P5569 [SDOI2008] 石子合并（省选/NOI−）
牛客竞赛	https://ac.nowcoder.com/acm/problem/collection/5789	区间dp（题单）
洛谷	https://www.luogu.com.cn/training/4901	区间DP（题单）
洛谷	https://www.luogu.com.cn/training/78058	区间DP（题单）

🗿 3.1 石子合并

链接：https://www.luogu.com.cn/problem/P1775
问题描述 设有 N 堆石子排成一排，其编号为 1..N。每堆石子有一定的质量。现在要将这 N 堆石子合并成为一堆。每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和。试找出一种合理的方法，使总的代价最小。
示例：
输入：4, 2 5 3 1
输出：22

(1) 核心思路

我们用 dp[i][j] 表示将第 i 堆到第 j 堆石子合并成一堆的最小代价。

(2) 状态转移方程

要计算 dp[i][j]，我们枚举最后一次合并的位置 k。即，区间 [i, j] 是由 [i, k] 和 [k+1, j] 这两个已经合并好的子堆最后一次合并而成的。

d p [i] [j] = min_{i \leq k < j} (d p [i] [k] + d p [k + 1] [j]) + cost (i, j)

其中 cost(i, j) 是将 i 到 j 的所有石子合并的代价，也就是 i 到 j 的石子总质量。我们可以用前缀和 s[] 快速计算：s[j] - s[i-1]。

最终方程：

d p [i] [j] = min_{i \leq k < j} (d p [i] [k] + d p [k + 1] [j] + s [j] - s [i - 1])

(3) 初始化与遍历

初始化：dp[i][i] = 0 (单堆石子无需合并，代价为0)。

遍历：区间 DP 的典型遍历方式是，先枚举区间长度 len (从2到n)，再枚举区间左端点 i，右端点 j 由 i + len - 1 确定。

(4) 参考代码

c++

#include <cstdio>
#include <iostream>
using namespace std;
const int N = 310;
const int INF = 0x3f3f3f3f;
int a[N], s[N];  // s[i]是前i堆石子的前缀和
int f[N][N];     // f[i][j] 表示的是从第i堆合并到第j堆，最小代价
int n;
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);

  // 计算合并的前缀和
  for (int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i];

  // 初始化, 区间长度为1时
  for (int i = 1; i <= n; i++) f[i][i] = 0;

  // 要按照区间从小到大得到 f[1][n],直接从2开始
  for (int len = 2; len <= n; len++)  // k表示枚举区间的长度
  {
    for (int i = 1; i + len - 1 <= n; i++)  // 枚举区间的左端点
    {
      int l = i, r = i + len - 1;  // 枚举左右端点
      f[l][r] = INF;
      for (int k = l; k < r; k++) {
        f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
      }
    }
  }
  printf("%d\n", f[1][n]);
  return 0;
}

🧮 4. 计数类DP问题

🗂️ 4.0 洛谷 & 牛客题单

来源	题目/题单	说明
背包思想⬇️	背包思想⬇️	背包思想⬇️
洛谷	https://www.luogu.com.cn/problem/U490083	U490083 整数划分问题
洛谷	https://www.luogu.com.cn/problem/T626668	T626668 整数划分
洛谷	https://www.luogu.com.cn/problem/T557819	T557819 06-02-C10-整数划分问题(递归求解)
洛谷	https://www.luogu.com.cn/problem/T170019	T170019 整数划分
计数dp⬇️	计数dp⬇️	计数dp⬇️
洛谷	https://www.luogu.com.cn/problem/U505981	U505981 整数划分
洛谷	https://www.luogu.com.cn/problem/U426896	U426896 整数划分
拓展⬇️	拓展⬇️	拓展⬇️
洛谷	https://www.luogu.com.cn/problem/P1025	P1025 [NOIP 2001 提高组] 数的划分
洛谷	https://www.luogu.com.cn/problem/U296470	U296470 420.整数划分
题单⬇️	题单⬇️	题单⬇️
洛谷	https://www.luogu.com.cn/training/188779	DP & 计数（题单）
洛谷	https://www.luogu.com.cn/training/321034	计数类DP（题单）

🍰 4.1 整数划分

问题描述：整数划分 一个正整数 n 可以表示成若干个正整数之和，形如：n = n1 + n2 + … + nk，其中 n1 ≥ n2 ≥ … ≥ nk, k ≥ 1。我们将这样的一种表示称为正整数 n 的一种划分。现在给定一个正整数 n，请你求出 n 共有多少种不同的划分方法。

🧠➡️ 4.1.1 思路1：完全背包模型

把1, 2, 3, ..., n 看做 n 种物品（数量无限），问体积恰好为 n 的总方案数。

（1）状态: f[i][j] 表示从前 i 个整数(1,2,…,i)中选择，和恰好为 j 的方案数。

（2）转移: f[i][j] = f[i-1][j] (不选i) + f[i][j-i] (选i)。

（3）优化: 可以用一维滚动数组实现。

（4）代码实现

c++

// 写法1：完全背包  二维
#include <iostream>
using namespace std;
const int N = 1010, mod = 1e9 + 7;
// f[i][j]表示从前i个数中选，总和恰好为j的划分方法的方案数
int f[N][N], n;

int main() {
  scanf("%d", &n);
  for (int i = 0; i <= n; ++i) f[i][0] = 1;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      if (j >= i)
        f[i][j] = (f[i - 1][j] + f[i][j - i]) % mod;
      else
        f[i][j] = f[i - 1][j] % mod;
    }
  }

  printf("%d\n", f[n][n]);
  return 0;
}

c++

// 完全背包，一维
#include <iostream>
using namespace std;
const int N = 1010, mod = 1e9 + 7;
int f[N], n;

int main() {
  scanf("%d", &n);
  f[0] = 1;
  for (int i = 1; i <= n; ++i)
    for (int j = i; j <= n; ++j) f[j] = (f[j] + f[j - i]) % mod;

  printf("%d\n", f[n]);
  return 0;
}

🔢💡4.1.2 思路2：计数DP

（1）状态: f[i][j] 表示总和为 i，且由 j 个正整数组成的方案数。

（2）转移: f[i][j] 的方案可以分为两类：

划分中包含 1：去掉这个 1，剩下 j-1 个数和为 i-1，方案数为 f[i-1][j-1]。

划分中不包含 1（即所有数都≥2）：将每个数都减 1，剩下 j 个数和为 i-j，方案数为 f[i-j][j]。即：

c++

f[i][j] = f[i-1][j-1] + f[i-j][j]

（3）代码实现 (计数DP)

c++

// 计数dp
#include <iostream>
using namespace std;
const int N = 1010, mod = 1e9 + 7;
int f[N][N], n;  // f[i][j]表示 总和是i，并且由j个数组成的方案数

int main() {
  scanf("%d", &n);
  f[0][0] = 1;
  for (int i = 1; i <= n; ++i)    // 枚举总和i  让总和从1枚举到n
    for (int j = 1; j <= i; ++j)  // 枚举整数的个数  从1枚举到n个数
      f[i][j] = (f[i - 1][j - 1] + f[i - j][j]) % mod;

  int ans = 0;
  for (int i = 1; i <= n; ++i) ans = (ans + f[n][i]) % mod;
  printf("%d\n", ans);

  return 0;
}

🔟 5. 数位统计DP问题

🗂️ 5.0 洛谷 & 牛客题单

来源	题目/题单	说明
牛客	https://www.nowcoder.com/practice/bb1a9efa244a4c9296390686ef17b024	[ZJOI2010]COUNT 数字计数
洛谷	https://www.luogu.com.cn/problem/P2602	P2602 [ZJOI2010] 数字计数
洛谷	https://www.luogu.com.cn/problem/T356040	T356040 [ZJOI2010] 数字计数
洛谷	https://www.luogu.com.cn/training/77987	数位DP（题单）
洛谷	https://www.luogu.com.cn/training/150651	数位dp（题单）
洛谷	https://www.luogu.com.cn/training/546190	数位统计DP（题单）
洛谷	https://www.luogu.com.cn/training/754747	数位统计DP（题单）
洛谷	https://www.luogu.com.cn/training/82023	（提高）『数位DP』从入门到入土（题单）

🔢 5.1 计数问题

P2602 [ZJOI2010] 数字计数：https://www.luogu.com.cn/problem/P2602
题目描述
给定两个正整数 $a$ 和 $b$ ，求在 $[a, b]$ 中的所有整数中，每个数码（digit）各出现了多少次。
输入格式
仅包含一行两个整数 $a, b$ ，含义如上所述。
输出格式
包含一行十个整数，分别表示 $0 \sim 9$ 在 $[a, b]$ 中出现了多少次。
输入输出样例
输入
1 99
1
输出
9 20 20 20 20 20 20 20 20 20
1
说明/提示，数据规模与约定
对于 $30 %$ 的数据，保证 $1 \leq a \leq b \leq 10^{6}$ ；
对于 $100 %$ 的数据，保证 $1 \leq a \leq b \leq 10^{12}$ 。

核心思路：前缀和思想 问题可以转化为 count(b) - count(a-1)，其中 count(n) 表示在 [1, n] 区间内数码的出现次数。

算法：按位分析 我们逐位计算每个数字 d (0-9) 出现的次数。对于一个数 n，我们分析它的每一位（从低到高）。假设 n = abc...defg，我们来计算第 i 位上数字 d 出现的次数。

高位部分 (abc...)
- 如果高位部分小于 abc... (例如 000... 到 abc...-1)，第 i 位可以任选 0-9，低位也可以任选 0-9。
当前位部分 (d)
- 如果当前位数字 d 大于要统计的数字 x，那么高位取 abc... 时，x 在这一位出现了 10^i 次。
- 如果当前位数字 d 等于 x，那么高位取 abc... 时，x 在这一位出现了 efg+1 次。
- 如果当前位数字 d 小于 x，则高位取 abc... 时，x 在这一位不可能出现。
特殊处理前导零

代码实现 (模板化)

写法1：

C++

#include <cmath>
#include <cstring>
#include <iostream>
typedef long long LL;
using namespace std;
LL dgt(LL n) {  // 计算整数n有多少位
  LL res = 0;
  while (n) ++res, n /= 10;
  return res;
}
LL cnt(LL n, int i) {  // 计算从1到n的整数中数字i出现多少次
  LL res = 0, d = dgt(n);
  for (LL j = 1; j <= d; ++j) {  // 从右到左第j位上数字i出现多少次
    // l和r是第j位左边和右边的整数 (视频中的abc和efg); dj是第j位的数字
    LL p = pow(10, j - 1), l = n / p / 10, r = n % p, dj = n / p % 10;
    // 计算第j位左边的整数小于l (视频中xxx = 000 ~ abc - 1)的情况
    if (i) res += l * p;
    if (!i && l)
      res += (l - 1) * p;  // 如果i = 0, 左边高位不能全为0 (视频中xxx = 001 ~ abc - 1)
    // 计算第j位左边的整数等于l (视频中xxx = abc)的情况
    if ((dj > i) && (i || l)) res += p;
    if ((dj == i) && (i || l)) res += r + 1;
  }
  return res;
}
int main() {
  LL a, b;
  scanf("%lld%lld", &a, &b);
  if (a > b) swap(a, b);
  for (int i = 0; i <= 9; ++i) { printf("%lld ", cnt(b, i) - cnt(a - 1, i)); }
  return 0;
}

写法2：

c++

#include <iostream>
#include <vector>

using namespace std;

int base[10];
int f[10][10];
int g[10][10];

void init() {
  base[0] = 1;
  for (int i = 1; i <= 9; i++) base[i] = base[i - 1] * 10;

  // 从00……0 - 99……9 的各位数字有多少个，其中i为数字个数（包含前导零）
  for (int i = 0; i <= 9; i++) f[1][i] = 1;
  for (int i = 2; i <= 9; i++)
    for (int j = 0; j <= 9; j++) f[i][j] = f[i - 1][j] * 10 + base[i - 1];

  // 从1 - 99……9 的各位数字有多少个，其中i为数字个数（不包含前导零）
  for (int i = 1; i <= 9; i++) g[1][i] = 1;  // 循环从1开始
  for (int i = 2; i <= 9; i++) {
    g[i][0] = g[i - 1][0] + f[i - 1][0] * 9;
    for (int j = 1; j <= 9; j++)
      g[i][j] = g[i - 1][j] + f[i - 1][j] * 9 + base[i - 1];
  }
}

vector<int> dp(int n) {
  vector<int> ans(10, 0);  // 记录答案
  if (n <= 0) return ans;  // 边界条件

  vector<int> nums;
  while (n) nums.push_back(n % 10), n /= 10;

  vector<int> last(10, 0);  // 记录前缀中各个数字个数

  // 统计1 - 99……9(n-1个9)里面各个数字有多少个
  for (int i = 0; i <= 9; i++) ans[i] = g[nums.size() - 1][i];
  // 统计大于10……0(n-1个0) 的树里各个数字有多少个
  for (int i = nums.size() - 1; i >= 0; i--) {
    // 循环变量i可以表示剩下的数字有多少个
    int x = nums[i];
    for (int j = i == nums.size() - 1; j < x; j++) {  // 第一次循环不能有0
      // 前缀部分
      for (int k = 0; k <= 9; k++) ans[k] += last[k] * base[i];
      // 当前位置部分
      ans[j] += base[i];
      // 后缀部分
      for (int k = 0; k <= 9; k++) ans[k] += f[i][k];
    }
    // 更新前缀计数器
    last[x]++;

    // 统计叶子节点（这个数本身）
    if (!i)
      for (int k = 0; k <= 9; k++) ans[k] += last[k];
  }
  return ans;
}

vector<int> ask(int a, int b) {
  auto x = dp(b);
  auto y = dp(a - 1);
  vector<int> ans;
  for (int i = 0; i <= 9; i++) ans.push_back(x[i] - y[i]);
  return ans;
}

void print(vector<int> ans) {
  for (auto x : ans) printf("%d ", x);
  puts("");
}

bool check(int x) {
  auto t = ask(x, x);
  vector<int> cnt(10, 0);
  while (x) cnt[x % 10]++, x /= 10;
  for (int i = 0; i <= 9; i++)
    if (cnt[i] != t[i]) return false;
  return true;
}

int main() {
  init();

  // 这里是一个DEBUG函数
  //  for(int i = 1 ; i <= 1000000 ; i*=10) {
  //      if(!check(i))
  //          printf("ERROR:%d\n",i);
  //  }

  int a, b;
  while (cin >> a >> b, a || b) {
    if (a > b) swap(a, b);
    auto t = ask(a, b);
    print(t);
  }

  return 0;
}

🗜️ 6. 状态压缩DP问题

🗂️ 6.0 洛谷 & 牛客题单

来源	题目/题单	说明
牛客竞赛	https://ac.nowcoder.com/acm/contest/1046/A	Mondriaan's Dream
洛谷	https://www.luogu.com.cn/problem/P10975	P10975 Mondriaan's Dream
洛谷	https://www.luogu.com.cn/problem/U204941	U204941 蒙德里安的梦想
洛谷	https://www.luogu.com.cn/problem/T164757	T164757 【状压】蒙德里安的梦想
洛谷	https://www.luogu.com.cn/problem/U396296	U396296 蒙德里安的梦想
洛谷	https://www.luogu.com.cn/problem/U606004	U606004 蒙德里安的梦想
洛谷	https://www.luogu.com.cn/problem/T575094	T575094 蒙德里安的梦想
洛谷	https://www.luogu.com.cn/problem/P10447	P10447 最短 Hamilton 路径
洛谷	https://www.luogu.com.cn/problem/U122241	U122241 最短Hamilton路径
洛谷	https://www.luogu.com.cn/problem/U211878	U211878 最短Hamilton路径
洛谷	https://www.luogu.com.cn/problem/U111875	U111875 最短Hamilton路径
洛谷	https://www.luogu.com.cn/problem/U207388	U207388 最短Hamilton路径
洛谷	https://www.luogu.com.cn/problem/U499137	U499137 最短Hamilton路径
洛谷	https://www.luogu.com.cn/training/75844	状压DP（题单）
洛谷	https://www.luogu.com.cn/training/213596	状压 dp 练习题（题单）
洛谷	https://www.luogu.com.cn/training/189397	状压dp（题单）
洛谷	https://www.luogu.com.cn/training/3121	状态压缩 dp（题单）
洛谷	https://www.luogu.com.cn/training/497743	Flaw_Owl 的状压 DP （题单）
洛谷	https://www.luogu.com.cn/training/43996	状压DP，数位DP（题单）

📜 6.1 状压DP介绍

NOTE

状态压缩动态规划（State Compression DP）是一种利用二进制位表示状态的技巧，常用于处理棋盘覆盖、铺砖、格子选择等具有“局部依赖”性质的问题。当问题的状态维度较高但每个维度取值较少（如只有 0/1）时，可以将整个状态压缩为一个整数（通常是 int 或 long long），从而在时间和空间上实现高效转移。

🎨 6.2 蒙德里安的梦想

P10975 Mondriaan's Dream：https://www.luogu.com.cn/problem/P10975

问题描述 用大小为 2×1 的小矩形（竖或横放）来填满一个 h × w 的大矩形，求所有不同铺法数量。1 ≤ h, w ≤ 11

这是一个经典的轮廓线 DP / 状态压缩 DP 问题。我们按列进行 DP，每一列的状态用一个长度为 h 的二进制数表示：

（1）状态定义：设 f[i][s] 表示处理到第 i 列，当前列的状态为 s 时的方案数。其中，s 是一个 h 位二进制数：

1、若第 j 位为 1，表示该位置已被上一列的横放骨牌覆盖（即当前列该位置是“突出”的，不能放新骨牌）；

2、若为 0，表示该位置空闲，需要被当前列或下一列的骨牌覆盖。

（2）关键观察：在从第 i-1 列转移到第 i 列时，必须保证两列拼接后能形成合法的铺法。也就是说，对于两个相邻列的状态 k（前一列）和 j（当前列），需满足：

1、j \& k = 0：不能有重叠的“突出”；

2、j | k 形成的空隙（即 0 的连续段）必须能被竖放或横放的骨牌填满——这等价于：所有连续的 0 段长度必须为偶数。

（3）预处理合法状态：我们预先计算所有 s \in [0, 2^h) 中哪些是“自身能被竖放骨牌填满”的状态（即没有孤立的 0）。但实际上，在转移中我们关心的是 j | k 是否能被填满，因此预处理 st[mask] 表示 mask 中所有连续 0 段长度是否为偶数。

3、代码解析

（1）预处理

c++

// 预处理 st[mask]：mask 中连续 0 的个数是否全为偶数
for (int i = 0; i < 1 << n; ++i) {
    st[i] = true;
    int cnt = 0;
    for (int j = 0; j < n; ++j) {
        if (i >> j & 1) {       // 遇到 1，检查前面连续 0 的长度
            if (cnt & 1) {      // 奇数个 0 → 无法用 2×1 骨牌填满
                st[i] = false;
                break;
            }
            cnt = 0;
        } else {
            ++cnt;
        }
    }
    if (cnt & 1) st[i] = false; // 最后一段 0 也要检查
}

（2）DP 转移：

c++

f[0][0] = 1;  // 初始：第 0 列，无突出，1 种方案
for (int i = 1; i <= m; ++i) {
    for (int j = 0; j < (1 << n); ++j) {        // 当前列状态 j
        for (int k = 0; k < (1 << n); ++k) {    // 上一列状态 k
            if (!(j & k) && st[j | k]) {
                f[i][j] += f[i - 1][k];
            }
        }
    }
}

最终答案：f[m][0]，表示处理完第 $m$ 列后，没有向右突出的状态（即完整铺满）。

（3）完整代码：

c++

#include <cstring>
#include <iostream>
using namespace std;
const int N = 12, M = 1 << N;
typedef long long LL;
LL f[N][M];  // f[i][mask]：填到第 i 列，列状态为 mask 的方案数
bool st[M];  // st[mask]：mask 是否为“能用竖条填满”的合法状态
int n, m;

int main() {
  while (scanf("%d%d", &n, &m) != EOF, n || m) {
    // 预处理所有合法状态（连续 0 数必须为偶数）
    for (int i = 0; i < 1 << n; ++i) {
      st[i] = true;
      int cnt = 0;
      for (int j = 0; j < n; ++j) {
        if (i >> j & 1) {  // 1 表示占用
          if (cnt & 1) {   // 出现奇数个 0，无法竖放
            st[i] = false;
            break;
          }
        } else
          ++cnt;  // 统计连续 0 的数量
      }
      if (cnt & 1) st[i] = false;
    }

    memset(f, 0, sizeof f);
    f[0][0] = 1;  // 初始：未开始且状态为 0

    // 按列进行 DP
    for (int i = 1; i <= m; ++i) {
      for (int j = 0; j < 1 << n; ++j) {    // 当前列状态
        for (int k = 0; k < 1 << n; ++k) {  // 上一列状态
          // j & k = 0：不能重叠
          // st[j | k]：合并状态可被竖条完全填满
          if (!(j & k) && st[j | k]) f[i][j] += f[i - 1][k];
        }
      }
    }

    printf("%lld\n", f[m][0]);  // 最终必须完全填满（状态=0）
  }

  return 0;
}

🗺️ 6.3 最短Hamilton路径

问题描述 给定一张 n 个点的无向带权图，求从起点 0 到终点 n-1，不重不漏经过每个点恰好一次的最短路径。数据范围 n ≤ 20。

(1) 核心思路 这是一个经典的旅行商问题（TSP）变种，由于 n <= 20，可以使用状态压缩 DP 解决。

(2) 状态定义f[s][j] 表示：

s: 一个 n 位的二进制数，表示已经访问过的节点集合（第 k 位为1表示节点 k 已访问）。
j: 当前所在的节点编号。
f[s][j] 的值：在访问了 s 集合中的所有节点，且当前停在节点 j 的情况下的最短路径长度。

(3) 状态转移方程 要计算 f[s][j]，我们可以枚举上一个访问的节点 k。 s' 是 s 去掉节点 j 后的状态，即 s' = s ^ (1 << j)。 f[s][j] = min(f[s'][k] + dist[k][j]) 其中 k 必须在集合 s' 中。

(4) 代码实现

c++

#include <cstring>
#include <iostream>
using namespace std;
const int N = 20;
// f[i][j]表示“点被经过的状态”对应的二进制数是i，且目前处于点j时的最短路径
int dist[N][N], f[1 << N][N], n;

int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < n; ++j) scanf("%d", &dist[i][j]);

  memset(f, 0x3f, sizeof f);
  f[1][0] = 0;  // 边界条件
  // i代表着是一个方案集合，其中每一个位置1和0，代表着这个点经过还是没有经过
  for (int i = 0; i < 1 << n; ++i) {
    for (int j = 0; j < n; ++j) {  // 枚举当前到了哪一个点
      if (i >> j & 1) {            // 如果i集合中第j位是1，也就是当前经过了j点
        for (int k = 0; k < n; ++k) {  // 枚举从哪个点k走到点j
          // 如果k和j是同一个点,则跳过
          if (k == j) continue;
          // 写法1：(i ^ 1 << j) >> k & 1
          // 写法2：(i & (~ (1 << j))) >> k & 1
          // 写法3：(i - (1 << j)) >> k & 1
          if ((i ^ 1 << j) >> k & 1)
            f[i][j] = min(f[i][j], f[i ^ 1 << j][k] + dist[k][j]);
        }
      }
    }
  }
  // 表示所有点都走过了,且终点是n-1的最短距离
  printf("%d\n", f[(1 << n) - 1][n - 1]);
  return 0;
}

🌳 7. 树形DP

🗂️ 7.0 洛谷 & 牛客题单

来源	题目/题单	说明
牛客	https://www.nowcoder.com/practice/45c6d97dfd1044769aed5d9d3f139be1	上司的舞会（与树形DP没啥关系）
牛客	https://www.nowcoder.com/practice/f703237089ee42d9b37e01d70e14e2fc	没有上司的舞会
洛谷	https://www.luogu.com.cn/problem/P1352	P1352 没有上司的舞会
洛谷	https://www.luogu.com.cn/problem/T589016	T589016 没有上司的舞会
洛谷	https://www.luogu.com.cn/problem/T575659	T575659 没有上司的舞会
洛谷	https://www.luogu.com.cn/problem/T160910	T160910 没有上司的舞会
洛谷	https://www.luogu.com.cn/problem/T570771	T570771 没有上司的舞会
洛谷	https://www.luogu.com.cn/problem/T413403	T413403 没有上司的舞会
题单⬇️	题单⬇️	题单⬇️
洛谷	https://www.luogu.com.cn/training/18506	树形DP模板题（题单）
洛谷	https://www.luogu.com.cn/training/196902	树形DP（题单）
洛谷	https://www.luogu.com.cn/training/11363	xzy的树形dp题单（题单）
洛谷	https://www.luogu.com.cn/training/7305	树形DP（题单）
洛谷	https://www.luogu.com.cn/training/13994	0x2 树形dp（题单）

🎉 7.1 没有上司的舞会

P1352 没有上司的舞会：https://www.luogu.com.cn/problem/P1352
题目描述
Ural大学有N名职员，编号为1~N。
他们的关系就像一棵以校长为根的树，父节点就是子节点的直接上司。
每个职员有一个快乐指数，用整数 Hi 给出，其中 1≤i≤N。
现在要召开一场周年庆宴会，不过，没有职员愿意和直接上司一起参会。
在满足这个条件的前提下，主办方希望邀请一部分职员参会，使得所有参会职员的快乐指数总和最大，求这个最大值。
输入格式
第一行一个整数N。
接下来N行，第 i 行表示 i 号职员的快乐指数Hi。
接下来N-1行，每行输入一对整数L, K,表示K是L的直接上司。
输出格式
输出最大的快乐指数。
数据范围
1≤N≤6000,
−128≤Hi≤127
输入样例：

7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5

输出样例：

5
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

(1) 核心思路 这是一个经典的树形DP问题。对于每个节点 u，我们考虑两种情况：u 参加舞会，或 u 不参加。

(2) 状态定义

dp[u][1]: 节点 u 参加舞会时，以 u 为根的子树能获得的最大快乐指数。
dp[u][0]: 节点 u 不参加舞会时，以 u 为根的子树能获得的最大快乐指数。

(3) 状态转移方程

如果 u 参加 (dp[u][1])：那么它的所有直接下属 v 都不能参加。 dp[u][1] = happy[u] + Σ dp[v][0] (v是u的子节点)
如果 u 不参加 (dp[u][0])：那么它的所有直接下属 v 可以参加，也可以不参加。我们为每个下属选择最优的情况。 dp[u][0] = Σ max(dp[v][0], dp[v][1]) (v是u的子节点)

(4) 实现 使用 DFS (深度优先搜索) 进行后序遍历，从叶子节点向上计算 DP 值。

(5) 代码实现

C++

#include <cstring>
#include <iostream>
using namespace std;
const int N = 6005;
int happy[N];
int h[N], e[N], ne[N], idx;
int dp[N][2];
bool has_father[N];  // 用于找出根结点是谁
void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx++; }
void dfs(int u) {
  dp[u][0] = 0;
  dp[u][1] = happy[u];
  for (int i = h[u]; i != -1; i = ne[i]) {
    int j = e[i];
    dfs(j);
    dp[u][0] += max(dp[j][0], dp[j][1]);
    dp[u][1] += dp[j][0];
  }
}
int main() {
  int n;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) { scanf("%d", happy + i); }
  memset(h, -1, sizeof(h));
  int a, b;
  for (int i = 0; i < n - 1; i++) {
    scanf("%d%d", &a, &b);
    has_father[a] = true;
    add(b, a);
  }
  // 找出根结点
  int root = 1;
  while (has_father[root]) { root++; }
  dfs(root);
  printf("%d", max(dp[root][0], dp[root][1]));
  return 0;
}

💾 8. 记忆化搜索

🗂️ 8.0 洛谷 & 牛客题单

来源	题目/题单	说明
牛客	https://www.nowcoder.com/practice/36d613e0d7c84a9ba3af3ab0047a35e0	滑雪
牛客	https://www.nowcoder.com/practice/7205912f04974f099714d8a49f78609d	滑雪
洛谷	https://www.luogu.com.cn/problem/P1434	P1434 [SHOI2002] 滑雪
洛谷	https://www.luogu.com.cn/problem/T281705	T281705 [SHOI2002] 滑雪

⛷️ 8.1 滑雪

P1434 [SHOI2002] 滑雪：https://www.luogu.com.cn/problem/P1434
题目描述
给定一个R行C列的矩阵，表示一个矩形网格滑雪场。
矩阵中第 i 行第 j 列的点表示滑雪场的第 i 行第 j 列区域的高度。
一个人从滑雪场中的某个区域内出发，每次可以向上下左右任意一个方向滑动一个单位距离。当然，一个人能够滑动到某相邻区域的前提是该区域的高度低于自己目前所在区域的高度。
下面给出一个矩阵作为例子：
1  2  3  4 5

16 17 18 19 6

15 24 25 20 7

14 23 22 21 8

13 12 11 10 9
1
2
3
4
5
6
7
8
9
在给定矩阵中，一条可行的滑行轨迹为24-17-2-1。
在给定矩阵中，最长的滑行轨迹为25-24-23-…-3-2-1，沿途共经过25个区域。
现在给定你一个二维矩阵表示滑雪场各区域的高度，请你找出在该滑雪场中能够完成的最长滑雪轨迹，并输出其长度(可经过最大区域数)。
输入格式
第一行包含两个整数R和C。
接下来R行，每行包含C个整数，表示完整的二维矩阵。
输出格式
输出一个整数，表示可完成的最长滑雪长度。
数据范围
1≤R,C≤300, 0≤矩阵中整数≤10000
输入样例：

5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9

输出样例：

25
1
2
3
4
5
6
7
8
9
10
11
12

(1) 核心思路 这是一个在 DAG（有向无环图）上求最长路径的问题。每个点 (i, j) 可以看作一个节点，从高处到低处的移动构成有向边。我们可以用记忆化搜索来解决，避免重复计算。

(2) 状态定义dp[x][y] 表示从点 (x, y) 出发能滑行的最长路径长度。

(3) 搜索过程 (DFS)dfs(x, y) 函数的逻辑：

检查记忆: 如果 dp[x][y] 已经计算过，直接返回。
初始化: dp[x][y] 初始为 1 (至少包含自己)。
探索邻居: 遍历 (x, y) 的四个邻居 (nx, ny)。
- 如果邻居合法 (在界内且高度更低)，则递归调用 dfs(nx, ny)，并更新当前点的最长路径： dp[x][y] = max(dp[x][y], dfs(nx, ny) + 1)
返回结果: 返回 dp[x][y]。

(4) 主函数 遍历所有点作为起点，调用 dfs 函数，取所有结果的最大值。

(5) 代码实现

写法1

c++

#include <bits/stdc++.h>
using namespace std;
const int N = 310;
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
int f[N][N], w[N][N], n, m;

int dfs(int x, int y) {
    int &v = f[x][y];
    if (v != -1)    return v;
    
    v = 1;
    for (int i = 0; i < 4; ++ i) {
        int a = x + dx[i], b = y + dy[i];
        if (a < 1 || a > n || b < 1 || b > m || w[a][b] >= w[x][y]) continue;
        v = max(v, dfs(a, b) + 1);
    }
    
    return v;
}

int main() {
    memset(f, -1, sizeof f);
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++ i)
        for (int j = 1; j <= m; ++ j)
            scanf("%d", &w[i][j]);
    
    int ans = 0;
    for (int i = 1; i <= n; ++ i)
        for (int j = 1; j <= m; ++ j)
            ans = max(ans, dfs(i, j));
    
    printf("%d\n", ans);
    return 0;
}

写法2（推荐）

c++

#include <cstring>
#include <iostream>
using namespace std;
const int N = 105;
// h[i][j] 表示地图上 (i, j) 位置的高度
// dp[i][j] 表示从 (i, j) 出发能滑行的最长路径长度（包括起点）
int h[N][N];
int dp[N][N];
int n, m;
// 四个方向：下、上、右、左
const int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

/**
 * @brief 记忆化搜索函数：计算从 (x, y) 出发的最长下降路径长度
 * @param x 当前行坐标
 * @param y 当前列坐标
 * @return 从 (x, y) 出发的最长路径长度
 */
int dfs(int x, int y) {
  // 如果已经计算过，直接返回结果（记忆化）
  if (dp[x][y] != 0) { return dp[x][y]; }

  // 初始路径长度为 1（至少包含自己）
  dp[x][y] = 1;

  // 尝试向四个方向移动
  for (int i = 0; i < 4; ++i) {
    int nx = x + dir[i][0];
    int ny = y + dir[i][1];

    // 检查是否在地图范围内，并且高度严格下降
    if (nx >= 0 && nx < n && ny >= 0 && ny < m && h[nx][ny] < h[x][y]) {
      // 递归求解邻居的最长路径，并更新当前点的结果
      dp[x][y] = max(dp[x][y], dfs(nx, ny) + 1);
    }
  }
  return dp[x][y];
}

int main() {
  // 输入地图大小
  scanf("%d%d", &n, &m);

  // 输入高度矩阵
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) { scanf("%d", &h[i][j]); }
  }

  // memset(dp, 0, sizeof(dp)); // 可选

  int ans = 0;

  // 枚举每个起点，求全局最长下降路径
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) { ans = max(ans, dfs(i, j)); }
  }

  printf("%d\n", ans);
  return 0;
}

第五讲 · 动态规划 原创 ​

🧠 第五讲 · 动态规划 ​

🎒 1. 背包问题 ​

📜 1.1 背包问题概述 ​

📦 1.2 01背包问题：每个物品最多选一次 ​

🗂️ 1.2.0 洛谷 & 牛客题单 ​

❓ 1.2.1 问题描述 ​

🧊 1.2.2 二维解法：朴素思想 ​

💡 1.2.3 一维解法：空间优化 ​

♾️ 1.3 完全背包问题：每个物品可选无限次 ​

🗂️ 1.3.0 洛谷 & 牛客题单 ​

❓ 1.3.1 问题描述 ​

🧊 1.3.2 二维DP数组解法 ​

💡 1.3.3 一维解法与遍历顺序 ​

🔢 1.4 多重背包问题：每个物品有数量上限 ​

🗂️ 1.4.0 洛谷 & 牛客题单 ​

❓ 1.4.1 问题描述 ​

🐌 1.4.2 朴素解法：转化为01背包 ​

🚀 1.4.3 二进制优化：高效拆分 ​

🚄 1.4.4 单调队列优化：终极方案 ​

🧩 1.5 分组背包问题：每组物品择一而从 ​

🗂️ 1.5.0 洛谷 & 牛客题单 ​

❓ 1.5.1 问题描述 ​

⚙️ 1.5.2 状态转移与实现 ​

✨ 1.6 背包问题变种 ​

🔢 1.6.1 求方案总数 ​

📝 1.6.2 求具体方案 ​

⚖️ 1.6.3 二维费用背包 ​

📊 1.7 总结 ​

🎯 1.7.1 核心区别 ​

📈 1.7.2 四大背包模型核心对比 ​

🔄 1.7.3 遍历顺序深度剖析 ​

⭐ 1.7.4 遍历顺序总结 ​

📏 2. 线性DP ​

📐 2.1 数字三角形 ​

📈 2.2 最长上升子序列 (LIS) ​

📎2.2.0 练习链接 ​

❓ 2.2.1 问题描述 ​

🐌 2.2.2 朴素版：动态规划 ​

⚡ 2.2.3 优化版：二分法 + 贪心 ​

📊 2.2.4 对比总结 ​

🔗 2.3 最长公共子序列 ​

✂️ 2.4 编辑距离 ​

↔️ 3. 区间DP ​

🗂️ 3.0 洛谷 & 牛客题单 ​

🗿 3.1 石子合并 ​

🧮 4. 计数类DP问题 ​

🗂️ 4.0 洛谷 & 牛客题单 ​

🍰 4.1 整数划分 ​

🧠➡️ 4.1.1 思路1：完全背包模型 ​

🔢💡4.1.2 思路2：计数DP ​

🔟 5. 数位统计DP问题 ​

🗂️ 5.0 洛谷 & 牛客题单 ​

🔢 5.1 计数问题 ​

🗜️ 6. 状态压缩DP问题 ​

🗂️ 6.0 洛谷 & 牛客题单 ​

📜 6.1 状压DP介绍 ​

🎨 6.2 蒙德里安的梦想 ​

🗺️ 6.3 最短Hamilton路径 ​

🌳 7. 树形DP ​

🗂️ 7.0 洛谷 & 牛客题单 ​

🎉 7.1 没有上司的舞会 ​

💾 8. 记忆化搜索 ​

🗂️ 8.0 洛谷 & 牛客题单 ​

⛷️ 8.1 滑雪 ​

第五讲 · 动态规划原创

🧠 第五讲 · 动态规划

🎒 1. 背包问题

📜 1.1 背包问题概述

📦 1.2 01背包问题：每个物品最多选一次

🗂️ 1.2.0 洛谷 & 牛客题单

❓ 1.2.1 问题描述

🧊 1.2.2 二维解法：朴素思想

💡 1.2.3 一维解法：空间优化

♾️ 1.3 完全背包问题：每个物品可选无限次

🗂️ 1.3.0 洛谷 & 牛客题单

❓ 1.3.1 问题描述

🧊 1.3.2 二维DP数组解法

💡 1.3.3 一维解法与遍历顺序

🔢 1.4 多重背包问题：每个物品有数量上限

🗂️ 1.4.0 洛谷 & 牛客题单

❓ 1.4.1 问题描述

🐌 1.4.2 朴素解法：转化为01背包

🚀 1.4.3 二进制优化：高效拆分

🚄 1.4.4 单调队列优化：终极方案

🧩 1.5 分组背包问题：每组物品择一而从

🗂️ 1.5.0 洛谷 & 牛客题单

❓ 1.5.1 问题描述

⚙️ 1.5.2 状态转移与实现

✨ 1.6 背包问题变种

🔢 1.6.1 求方案总数

📝 1.6.2 求具体方案

⚖️ 1.6.3 二维费用背包

📊 1.7 总结

🎯 1.7.1 核心区别

📈 1.7.2 四大背包模型核心对比

🔄 1.7.3 遍历顺序深度剖析

⭐ 1.7.4 遍历顺序总结

📏 2. 线性DP

📐 2.1 数字三角形

📈 2.2 最长上升子序列 (LIS)

📎2.2.0 练习链接

❓ 2.2.1 问题描述

🐌 2.2.2 朴素版：动态规划

⚡ 2.2.3 优化版：二分法 + 贪心

📊 2.2.4 对比总结

🔗 2.3 最长公共子序列

✂️ 2.4 编辑距离

↔️ 3. 区间DP

🗂️ 3.0 洛谷 & 牛客题单

🗿 3.1 石子合并

🧮 4. 计数类DP问题

🗂️ 4.0 洛谷 & 牛客题单

🍰 4.1 整数划分

🧠➡️ 4.1.1 思路1：完全背包模型

🔢💡4.1.2 思路2：计数DP

🔟 5. 数位统计DP问题

🗂️ 5.0 洛谷 & 牛客题单

🔢 5.1 计数问题

🗜️ 6. 状态压缩DP问题

🗂️ 6.0 洛谷 & 牛客题单

📜 6.1 状压DP介绍

🎨 6.2 蒙德里安的梦想

🗺️ 6.3 最短Hamilton路径

🌳 7. 树形DP

🗂️ 7.0 洛谷 & 牛客题单

🎉 7.1 没有上司的舞会

💾 8. 记忆化搜索

🗂️ 8.0 洛谷 & 牛客题单

⛷️ 8.1 滑雪