算法笔记:AcWing - 动态规划(其他 DP 模型)

Ginkgo True love prevails.

💡 写在前面:动态规划不是背模板,而是学会”如何思考”。遇到任何 DP 问题,都按这个框架走:状态表示 → 状态转移 → 初始化 → 优化。下面我会用这个框架拆解每种模型,让你真正理解而不是死记硬背。


线性 DP

核心特征:递推方程有明显的线性关系,状态通常沿着某个方向(从左到右、从上到下)依次推进。

📐 数字三角形

问题描述:给定一个数字三角形,从顶部出发,每次可以向左下或右下移动,求到达底部时路径上的数字之和最大是多少。

1
2
3
4
5
    7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

为什么用 DP? 因为每个位置的最优解只依赖于上一层的两个位置,具有最优子结构和重叠子问题。

思考框架:

  1. 状态表示

    • f[i][j] 表示什么?→ 从顶点走到第 i 行第 j 列的所有路径中,最大路径权重和
    • 集合是什么?→ 所有从起点走到 (i, j) 的路径集合
    • 属性是什么?→ max(最大值)
  2. 状态转移(核心!)

    • 如何划分子问题?→ 考虑”最后一步”是从哪里来的
    • 能走到 (i, j) 的位置只有两个:(i-1, j-1) 和 (i-1, j)
    • 转移方程:
  3. 初始化

    • 边界条件:f[1][1] = w[1][1]
    • 为了防止从非法位置转移,把边界外初始化为 -INF
  4. 优化

    • 可以用滚动数组优化空间,但这题 N ≤ 500,不需要
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
const int N = 510, INF = 1e9;
int n;
int w[N][N], f[N][N];

int main() {
cin >> n;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= i; j++)
cin >> w[i][j];

// 初始化边界(重要!防止从非法位置转移)
for (int i = 0; i <= n; i++)
for (int j = 0; j <= i + 1; j++)
f[i][j] = -INF;

f[1][1] = w[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]) + w[i][j];

// 答案在最后一行的最大值
cout << *max_element(f[n] + 1, f[n] + n + 1);
}

时间复杂度:状态数 × 转移次数 =


📈 最长上升子序列 (LIS)

问题描述:给定一个长度为 N 的数列,求数值严格单调递增的子序列的长度最长是多少。

直观理解:想象你有一串数字,要从中挑出一些数字排成一队,要求后面的数字必须比前面的大,问这队人最多能有多长。

思考框架:

  1. 状态表示

    • f[i] 表示什么?→ 以第 i 个数结尾的最长上升子序列长度
    • 为什么这样定义?→ 因为上升子序列必须有个”结尾”,固定结尾才能讨论前面的选择
  2. 状态转移

    • 如何划分子问题?→ 考虑 a[i] 前面可以接哪个数
    • 枚举 j < i,如果 a[j] < a[i],则 a[i] 可以接在 a[j] 后面
    • 转移方程:
  3. 初始化

    • 每个位置最差也是”只有自己”,所以 f[i] = 1
  4. 答案

    • 不一定是 f[n],而是所有 f[i] 的最大值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
const int N = 1010;
int n;
int a[N], f[N];

int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
f[i] = 1; // 初始化:最差也是自身一个
}

for (int i = 1; i <= n; i++)
for (int j = 1; j < i; j++)
if (a[i] > a[j])
f[i] = max(f[i], f[j] + 1);

// 答案不一定是 f[n],要取最大值
int ans = 0;
for (int i = 1; i <= n; i++) ans = max(ans, f[i]);
cout << ans;
}

时间复杂度:


🎯 如何输出最长序列本身?

思路:记录每个位置是从哪个位置转移过来的,最后倒着回溯。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
const int N = 1010;
int n;
int a[N], f[N], g[N]; // g[i] 记录 i 是从哪个位置转移来的

int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
f[i] = 1;
}

for (int i = 1; i <= n; i++)
for (int j = 1; j < i; j++)
if (a[i] > a[j] && f[i] < f[j] + 1) {
f[i] = f[j] + 1;
g[i] = j; // 记录转移来源
}

// 找到最长序列的结尾位置
int k = 1;
for (int i = 1; i <= n; i++)
if (f[k] < f[i]) k = i;

cout << f[k] << endl;

// 倒序输出序列
vector<int> path;
while (k) {
path.push_back(a[k]);
k = g[k];
}
reverse(path.begin(), path.end());
for (int x : path) cout << x << " ";
}

🔗 最长公共子序列 (LCS)

问题描述:给定两个字符串,求它们的最长公共子序列的长度。

易错点:f[i][j] 表示的是 str1 的前 i 个字符和 str2 的前 j 个字符的 LCS,不一定是以 i 和 j 结尾!

思考框架:

  1. 状态表示

    • f[i][j] → str1[1..i] 和 str2[1..j] 的最长公共子序列长度
  2. 状态转移(关键!)

    • 考虑 str1[i] 和 str2[j] 是否在 LCS 中,分四种情况:

      • 都不用:f[i-1][j-1]
      • 不用 str1[i]:f[i-1][j]
      • 不用 str2[j]:f[i][j-1]
      • 都用(仅当 str1[i] == str2[j]):f[i-1][j-1] + 1
    • 注意:f[i-1][j-1] 被包含在 f[i-1][j] 和 f[i][j-1] 中,可以省略

    • 转移方程:

      默认至少丢一个如果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const int N = 1010;
int f[N][N];

int main() {
int n, m;
cin >> n >> m;
string str1, str2;
cin >> str1 >> str2;

for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
f[i][j] = max(f[i - 1][j], f[i][j - 1]);
if (str1[i-1] == str2[j-1]) // 注意 string 是 0-base
f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
}

cout << f[n][m];
}

时间复杂度:


✏️ 编辑距离

问题描述:给定两个字符串 A 和 B,可以对 A 进行三种操作:插入一个字符、删除一个字符、替换一个字符。求把 A 变成 B 的最少操作次数。

直观理解:想象你在改作文,老师让你把一句话改成另一句,你希望改动越少越好。

思考框架:

  1. 状态表示

    • f[i][j] → 把 A 的前 i 个字符变成 B 的前 j 个字符的最少操作次数
  2. 状态转移

    • 考虑最后一步操作是什么:

      • 删除 A[i]:f[i-1][j] + 1
      • 插入 B[j]:f[i][j-1] + 1
      • 替换 A[i] 为 B[j]:如果 A[i] == B[j] 则 f[i-1][j-1],否则 f[i-1][j-1] + 1
    • 转移方程:

      删除插入替换匹配

  3. 初始化

    • f[i][0] = i:把 A 的前 i 个字符变成空串,需要删除 i 次
    • f[0][j] = j:把空串变成 B 的前 j 个字符,需要插入 j 次
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
const int N = 1010;
int f[N][N];

int main() {
int n, m;
cin >> n >> m;
string a, b;
cin >> a >> b;

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

for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1); // 删除或插入
f[i][j] = min(f[i][j], f[i - 1][j - 1] + (a[i-1] != b[j-1])); // 替换或匹配
}

cout << f[n][m];
}

应用场景:

  • 拼写检查(计算单词相似度)
  • DNA 序列比对
  • 版本控制中的差异比较

时间复杂度:


区间 DP

核心特征:状态表示的是一个区间 [i, j],通常通过枚举区间的分割点来转移。

典型问题:合并类问题、回文相关、括号匹配等。


🪨 石子合并

问题描述:有 N 堆石子排成一排,每次只能合并相邻的两堆,合并的代价是两堆石子的数量之和。求把所有石子合并成一堆的最小总代价。

为什么难? 因为合并顺序不同,代价不同。比如 (1,2,3):

  • 先合并 (1,2) 再合并 (3,3):代价 3 + 6 = 9
  • 先合并 (2,3) 再合并 (1,5):代价 5 + 6 = 11

思考框架:

  1. 状态表示

    • f[i][j] → 把第 i 堆到第 j 堆石子合并成一堆的最小代价
  2. 状态转移(核心思想:考虑最后一次合并)

    • 最后一次合并一定是把 [i, k] 和 [k+1, j] 两堆合并
    • 枚举分界点 k(i ≤ k < j)
    • 转移方程:
    • 其中 sum(i, j) 是区间和,用前缀和优化
  3. 枚举顺序(关键!)

    • 必须按区间长度从小到大枚举
    • 因为大区间的解依赖于小区间的解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
const int N = 310, INF = 1e9;
int n;
int s[N]; // 前缀和
int f[N][N]; // f[i][j] 表示合并 [i,j] 的最小代价

int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> s[i];
s[i] += s[i - 1]; // 前缀和
}

// 按区间长度从小到大
for (int len = 2; len <= n; len++) {
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]);
}
}
}

cout << f[1][n];
}

时间复杂度:(三层循环:长度、左端点、分界点)

记忆口诀:区间 DP 三板斧——① 按长度枚举 ② 枚举左端点 ③ 枚举分割点


计数 DP

核心特征:求方案数而不是最优值,通常用加法原理或乘法原理转移。


🔢 整数划分

问题描述:把正整数 n 表示成若干个正整数之和,求方案数。例如 4 的划分:

1
2
3
4
5
4
3 + 1
2 + 2
2 + 1 + 1
1 + 1 + 1 + 1

共 5 种方案。

解法一:看作完全背包

把 1, 2, 3, ..., n 看作物品,每个物品可以选无限次,求装满容量 n 的方案数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
const int N = 1010, MOD = 1e9 + 7;
int n;
int f[N]; // f[j] 表示凑出 j 的方案数

int main() {
cin >> n;
f[0] = 1; // 凑出 0 有一种方案:什么都不选

for (int i = 1; i <= n; i++) // 枚举物品
for (int j = i; j <= n; j++) // 正序枚举容量(完全背包)
f[j] = (f[j] + f[j - i]) % MOD;

cout << f[n];
}

解法二:按最小数分类

  • f[i][j] 表示用 j 个数凑出 i 的方案数
  • 转移:考虑最小的数是不是 1
    • 如果最小数是 1:去掉这个 1,变成 f[i-1][j-1]
    • 如果最小数 > 1:所有数都减 1,变成 f[i-j][j]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const int N = 1010, MOD = 1e9 + 7;
int n;
int f[N][N];

int main() {
cin >> n;
f[0][0] = 1;

for (int i = 1; i <= n; i++)
for (int j = 1; j <= i; j++)
f[i][j] = (f[i - 1][j - 1] + f[i - j][j]) % MOD;

int ans = 0;
for (int j = 1; j <= n; j++)
ans = (ans + f[n][j]) % MOD;

cout << ans;
}

时间复杂度:解法一 ,解法二


数位统计 DP

核心特征:统计某个范围内满足特定条件的数字个数,通常按位拆分、分类讨论。

典型问题:求 [a, b] 范围内数字 x 出现了多少次。


🔍 核心思路

定义函数 count(n, x) = 1 ~ n 中数字 x 出现的次数,则答案为:

关键技巧:按位拆分

把 n 按某一位拆成三部分:高位 + 当前位 + 低位

例如 n = abcdefg,考虑第 4 位(数字 d):

1
2
  a   b   c   d   e   f   g
高位 当前 低位

设:

  • high = n / 10^(k+1)(高位)
  • cur = 当前位数字
  • low = n % 10^k(低位)
  • pow10 = 10^k

分类讨论(x ≠ 0 时):

情况 条件 贡献
1 cur > x (high + 1) × pow10
2 cur == x high × pow10 + (low + 1)
3 cur < x high × pow10

特殊情况:x = 0

0 不能作为前导零,所以高位不能为 0:

  • high 需要减 1
  • 如果 high == 0,直接跳过
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
typedef long long i64;

i64 count(i64 n, int x) {
if (n == 0) return 0;

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

i64 res = 0;
int len = nums.size();

for (int i = len - 1; i >= 0; i--) {
i64 pow10 = 1;
for (int j = 0; j < i; j++) pow10 *= 10;

i64 high = 0;
for (int j = len - 1; j > i; j--)
high = high * 10 + nums[j];

int cur = nums[i];

i64 low = 0;
for (int j = i - 1; j >= 0; j--)
low = low * 10 + nums[j];

if (x != 0) {
if (cur > x) res += (high + 1) * pow10;
else if (cur == x) res += high * pow10 + (low + 1);
else res += high * pow10;
} else {
if (high == 0) continue; // 跳过前导零
if (cur > 0) res += high * pow10;
else res += (high - 1) * pow10 + (low + 1);
}
}
return res;
}

int main() {
i64 a, b;
while (cin >> a >> b, a || b) {
if (a > b) swap(a, b);
for (int i = 0; i <= 9; i++)
cout << count(b, i) - count(a - 1, i) << " ";
cout << '\n';
}
}

💡 理解技巧:想象你在填数字,对于每一位,统计这一位是 x 的情况下,其他位有多少种填法。


状态压缩 DP

核心特征:用一个整数的二进制位来表示一种状态,通常用于集合类问题。

适用场景:

  • 元素个数较少(通常 n ≤ 20)
  • 需要表示”哪些元素被选过”
  • 棋盘铺砖、旅行商问题等

🧩 蒙德里安的梦想

问题描述:用 1×2 的小木块铺满 n×m 的棋盘,求方案数。木块可以横放或竖放。

核心洞察:横放的木块决定了竖放的木块!

想象一下:如果你确定了所有横放木块的位置,那么剩下的空位只能竖着放,而且必须能刚好填满。所以问题转化为:有多少种合法的横放方案?

状态表示:

  • f[i][j]:前 i 列,第 i 列的状态为 j 的方案数
  • j 是一个二进制数,第 k 位为 1 表示第 k 行有一个横放木块的右端

合法条件:

  1. j & k == 0:当前列和前一列的横放木块不能重叠
  2. j | k 中不能有连续奇数个 0:否则竖放木块填不满
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
const int N = 12, M = 1 << N;
int n, m;
long long f[N][M];
bool st[M]; // st[i] 表示状态 i 是否有连续奇数个 0

int main() {
while (cin >> n >> m, n || m) {
memset(f, 0, sizeof f);

// 预处理:哪些状态有连续奇数个 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) {
if (cnt & 1) st[i] = false; // 奇数个 0
cnt = 0;
} else {
cnt++;
}
}
if (cnt & 1) st[i] = false;
}

f[0][0] = 1;
for (int i = 1; i <= m; i++)
for (int j = 0; j < 1 << n; j++)
for (int k = 0; k < 1 << n; k++)
if ((j & k) == 0 && st[j | k])
f[i][j] += f[i - 1][k];

cout << f[m][0] << '\n'; // 最后一列不能有横放木块伸出
}
}

时间复杂度:


🚗 最短哈密顿路径

问题描述:给定 n 个点,求从点 0 出发,经过所有点恰好一次,最后到达点 n-1 的最短路径。

暴力做法:枚举所有排列,,n=20 时直接爆炸。

状压 DP:用二进制表示”哪些点已经走过”。

状态表示:

  • f[i][j]:已经走过的点集为 i,当前在点 j 的最短路径长度
  • i 是二进制状态,如 i = (10010)_2 表示第 1、4 个点走过

状态转移:

  • 考虑”最后一步”是从哪个点 k 走到 j 的
  • 转移方程:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
const int N = 20, M = 1 << N, INF = 0x3f3f3f3f;
int n;
int w[N][N]; // 邻接矩阵
int f[M][N]; // f[状态][当前点]

int main() {
cin >> n;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
cin >> w[i][j];

memset(f, 0x3f, sizeof f);
f[1][0] = 0; // 初始状态:只走过点 0,在点 0

for (int i = 0; i < 1 << n; i++)
for (int j = 0; j < n; j++)
if (i >> j & 1) // 点 j 在状态 i 中
for (int k = 0; k < n; k++)
if ((i - (1 << j)) >> k & 1) // 点 k 在 i-{j} 中
f[i][j] = min(f[i][j], f[i - (1 << j)][k] + w[k][j]);

cout << f[(1 << n) - 1][n - 1]; // 所有点都走过,终点是 n-1
}

时间复杂度:


🖥️ 分布式任务调度

问题描述:N 个任务,每个任务有 (CPU, 内存,价值)。每台服务器有 CPU 上限 C、内存上限 M。对于 K = 1..N,分别求有 K 台服务器时可获得的最大总价值。

核心思路:

  1. 预处理哪些任务子集可以被一台服务器处理
  2. DP:dp[k][s] 表示 k 台服务器处理任务集合 s 的最大价值

关键技巧:

  • lb = s & -s:取出最低位的 1(lowbit)
  • __builtin_ctz(lb):计算 lb 末尾 0 的个数,即第几个任务
  • 枚举子集:for (int sub = s; sub; sub = (sub - 1) & s)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
struct Task {
int c, m, v;
};

int main() {
int n, c, m;
cin >> n >> c >> m;
vector<Task> tasks(n);
for (int i = 0; i < n; i++)
cin >> tasks[i].c >> tasks[i].m >> tasks[i].v;

int S = 1 << n;
vector<int> sumc(S, 0), summ(S, 0), sumv(S, 0);
vector<bool> ok(S, false);

// 预处理:哪些子集可以被一台服务器处理
for (int s = 1; s < S; s++) {
int lb = s & -s; // lowbit
int i = __builtin_ctz(lb); // 第几个任务
int prev = s ^ lb; // 去掉最低位的 1

sumc[s] = sumc[prev] + tasks[i].c;
summ[s] = summ[prev] + tasks[i].m;
sumv[s] = sumv[prev] + tasks[i].v;

if (sumc[s] <= c && summ[s] <= m)
ok[s] = true;
}

int dp[n + 1][S];
memset(dp, 0, sizeof dp);

for (int k = 1; k <= n; k++) {
for (int s = 0; s < S; s++) {
dp[k][s] = dp[k - 1][s]; // 第 k 台服务器不处理任何任务
// 枚举 s 的子集 sub
for (int sub = s; sub; sub = (sub - 1) & s) {
if (ok[sub])
dp[k][s] = max(dp[k][s], dp[k - 1][s ^ sub] + sumv[sub]);
}
}
}

for (int k = 1; k <= n; k++)
cout << dp[k][S - 1] << '\n';
}

子集枚举技巧:

1
2
3
4
// 从大到小枚举 s 的所有子集
for (int sub = s; sub; sub = (sub - 1) & s) {
// sub 依次是 s 的各个子集
}

树形 DP

核心特征:在树结构上进行 DP,通常用 DFS 遍历,状态表示以某个节点为根的子树。

典型问题:树上的最大独立集、树的重心、树的直径等。


💃 没有上司的舞会

问题描述:公司要开舞会,员工之间有上下级关系(形成树形结构)。如果邀请了某个员工,就不能邀请他的直接上司。求能邀请的员工的最大快乐值总和。

思考框架:

  1. 状态表示

    • f[u][0]:以 u 为根的子树,不选 u 的最大快乐值
    • f[u][1]:以 u 为根的子树,选 u 的最大快乐值
  2. 状态转移

    • 不选 u:子节点可选可不选,取最大值
    • 选 u:子节点都不能选
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
const int N = 6010;
int n;
int happy[N];
int h[N], e[N], ne[N], idx;
int f[N][2];
bool has_fa[N];

void add(int u, int v) {
e[idx] = v, ne[idx] = h[u], h[u] = idx++;
}

void dfs(int u) {
f[u][1] = happy[u]; // 选 u,加上 u 的快乐值
for (int i = h[u]; i != -1; i = ne[i]) {
int j = e[i];
dfs(j);
f[u][0] += max(f[j][0], f[j][1]); // 不选 u,子节点随便
f[u][1] += f[j][0]; // 选 u,子节点不能选
}
}

int main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> happy[i];

memset(h, -1, sizeof h);
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
has_fa[u] = true;
add(v, u); // v 是 u 的上司
}

// 找根节点(没有上司的人)
int root = 1;
while (has_fa[root]) root++;

dfs(root);
cout << max(f[root][0], f[root][1]);
}

时间复杂度:(每个节点访问一次)


记忆化搜索

核心思想:用递归的方式实现 DP,用数组记录已经计算过的状态,避免重复计算。

本质:记忆化搜索 = 递归 + 缓存,和递推 DP 是等价的,只是实现方式不同。

适用场景:

  • 状态转移不容易用循环表示
  • 有些状态可能访问不到(记忆化搜索只计算需要的状态)
  • 代码更直观、更好写

⛷️ 滑雪

问题描述:给定一个 R×C 的高度矩阵,可以从高处滑向低处(上下左右四个方向),求最长的滑行路径长度。

思考框架:

  1. 状态表示

    • f[i][j]:从 (i, j) 出发能滑行的最长路径长度
  2. 状态转移

    • 可以向四个方向滑,前提是目标位置高度更低
    • f[i][j] = 1 + max(f[相邻且更低的位置])
  3. 记忆化

    • 如果 f[i][j] 已经计算过(不为 -1),直接返回
    • 否则递归计算并保存结果
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
const int N = 310;
int n, m;
int h[N][N];
int f[N][N]; // 记忆化数组
int dx[4] = {0, -1, 0, 1}, dy[4] = {1, 0, -1, 0};

int dp(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 && h[x][y] > h[a][b])
v = max(v, dp(a, b) + 1);
}
return v;
}

int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> h[i][j];

memset(f, -1, sizeof f);

int res = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
res = max(res, dp(i, j)); // 枚举起点

cout << res;
}

为什么叫”记忆化”搜索? 因为每次递归前先”查记忆”(看是否算过),算完后”写记忆”(保存结果)。

时间复杂度:(每个状态只计算一次)


📝 总结

DP 模型 状态特征 典型问题 时间复杂度
线性 DP 一维或二维线性推进 LIS、LCS、数字三角形
区间 DP 区间 [i, j] 石子合并、回文
计数 DP 求方案数 整数划分
数位 DP 按位拆分 数字统计
状压 DP 二进制状态 铺砖、TSP
树形 DP 树的子树 最大独立集
记忆化搜索 递归 + 缓存 滑雪、迷宫 视情况而定

核心心法:

  1. 状态表示要清晰:f[...] 到底表示什么?
  2. 状态转移要想”最后一步”:怎么从子问题推过来?
  3. 初始化不能忘:边界条件是什么?
  4. 枚举顺序要对:大状态依赖的小状态要先算完

🍂 最后的话:DP 不是背模板,而是培养一种”分解问题”的思维方式。多做题、多总结,你会发现 DP 其实很有规律。加油!

  • Title: 算法笔记:AcWing - 动态规划(其他 DP 模型)
  • Author: Ginkgo
  • Created at : 2026-04-12 10:20:20
  • Updated at : 2026-04-26 22:05:15
  • Link: https://g1nkgo7.github.io/2026/04/12/算法笔记-AcWing-动态规划(其他dp模型)/
  • License: This work is licensed under CC BY-NC-SA 4.0.
Comments
On this page
算法笔记:AcWing - 动态规划(其他 DP 模型)