00:00:00
左神学习笔记3
2026.05.13开始学习
2026.05.13 20:33:00
算法讲解066【必备】从递归入手一维动态规划
1、前置知识
前置知识:
需要熟悉递归，如果不熟悉如下课程都涉及递归，
讲解017、讲解020、讲解021、讲解022、讲解023
讲解036、讲解037、讲解038、讲解039、讲解040
关于取模，
讲解041-同余原理
本节课我们从基本递归入手，来了解一维动态规划
注意：
重叠子问题？最优子结构？无后效性？
此时谈这些太早，【必备】阶段动态规划的大总结，将在动态规划专题结束时进行
2、内容
动态规划：用空间代替重复计算，包含一整套原理和技巧的总和，课程会用非常大的篇幅来全盘介绍
知道怎么算的算法 vs 知道怎么试的算法
有些递归在展开计算时，总是重复调用同一个子问题的解，这种重复调用的递归变成动态规划很有收益
如果每次展开都是不同的解，或者重复调用的现象很少，那么没有改动态规划的必要
下节课会举例，哪些递归没有必要改动态规划的必要
所以任何动态规划的题目都一定可以从递归入手，逐渐实现动态规划的方法
题目1到题目4，都从递归入手，逐渐改出动态规划的实现
尝试策略 就是 转移方程，完全一回事！
推荐从尝试入手，因为代码好写，并且一旦发现尝试错误，重新想别的递归代价轻！
当熟悉了从递归到动态规划的转化过程
那么就可以纯粹用动态规划的视角来分析问题了
题目5到题目8，都是纯粹用动态规划的视角来分析、优化的
如果不熟悉这个过程，直接一上来就硬去理解状态转移方程
那么往往会步履维艰、邯郸学步、东施效颦
这是多年教学看到的真实情况
很多极为优异的想法、设计和优化 来自 努力 or 天赋
建议脚踏实地，真正做好从递归到动态规划的练习
接下来的几节课也都会从最基本递归入手，逐渐写出动态规划的版本
：
想出设计优良的递归尝试
-> 记忆化搜索(从顶到底的动态规划) ，
-> 严格位置依赖的动态规划(从底到顶的动态规划) ，更多是为了下面说的
进一步优化空间（），一维、二维、多维动态规划都存在这种优化
解决一个问题，可能有很多尝试方法
众多的尝试方法中，可能若干的尝试方法有重复调用的情况，可以转化成动态规划
若干个可以转化成动态规划的方法中，又可能有优劣之分
判定哪个是最优的动态规划方法，依据来自题目具体参数的数据量
最优的动态规划方法实现后，后续又有一整套的优化技巧
本系列课程从【必备】到【扩展】到【挺难】都会讲动态规划，会把这一话题做全面的讲述
3、题目
题目1
斐波那契数
斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列
该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。
也就是：F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1
给定 n ，请计算 F(n)
测试链接 : https://leetcode.cn/problems/fibonacci-number/
注意：
斐波那契数问题最经典，本节课讲述的方法时间复杂度O(n)
但是最优解来自矩阵快速幂，时间复杂度可以做到O(log n)
矩阵快速幂后续课程一定会讲述！本节课不再展开
题目2
最低票价
在一个火车旅行很受欢迎的国度，你提前一年计划了一些火车旅行
在接下来的一年里，你要旅行的日子将以一个名为 days 的数组给出
每一项是一个从 1 到 365 的整数
火车票有 三种不同的销售方式
一张 为期1天 的通行证售价为 costs[0] 美元
一张 为期7天 的通行证售价为 costs[1] 美元
一张 为期30天 的通行证售价为 costs[2] 美元
通行证允许数天无限制的旅行
例如，如果我们在第 2 天获得一张 为期 7 天 的通行证
那么我们可以连着旅行 7 天(第2~8天)
返回 你想要完成在给定的列表 days 中列出的每一天的旅行所需要的最低消费
测试链接 : https://leetcode.cn/problems/minimum-cost-for-tickets/
题目3
解码方法
一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：
'A' -> "1"、'B' -> "2" ...'Z' -> "26"
要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）
例如，"11106" 可以映射为："AAJF"、"KJF"
注意，消息不能分组为(1 11 06)，因为 "06" 不能映射为 "F"
这是由于 "6" 和 "06" 在映射中并不等价
给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数
题目数据保证答案肯定是一个 32位 的整数
测试链接 : https://leetcode.cn/problems/decode-ways/
题目4
解码方法 II
一条包含字母 A-Z 的消息通过以下的方式进行了 编码 ：
'A' -> "1"、'B' -> "2" ...'Z' -> "26"
要 解码 一条已编码的消息，所有的数字都必须分组
然后按原来的编码方案反向映射回字母，可能存在多种方式。例如"11106" 可以映射为："AAJF"、"KJF"
注意，像 (1 11 06) 这样的分组是无效的，"06"不可以映射为'F'
除了上面描述的数字字母映射方案，编码消息中可能包含 '*' 字符
可以表示从 '1' 到 '9' 的任一数字（不包括 '0'）
例如，"1*" 可以表示 "11"、"12"、"13"、"14"、"15"、"16"、"17"、"18" 或 "19"
对 "1*" 进行解码，相当于解码该字符串可以表示的任何编码消息
给你一个字符串 s ，由数字和 '*' 字符组成，返回 解码 该字符串的方法 数目
由于答案数目可能非常大，返回10^9 + 7的模
测试链接 : https://leetcode.cn/problems/decode-ways-ii/
题目4
解码方法 II
一条包含字母 A-Z 的消息通过以下的方式进行了 编码 ：
'A' -> "1"、'B' -> "2" ...'Z' -> "26"
要 解码 一条已编码的消息，所有的数字都必须分组
然后按原来的编码方案反向映射回字母，可能存在多种方式。例如"11106" 可以映射为："AAJF"、"KJF"
注意，像 (1 11 06) 这样的分组是无效的，"06"不可以映射为'F'
除了上面描述的数字字母映射方案，编码消息中可能包含 '*' 字符
可以表示从 '1' 到 '9' 的任一数字（不包括 '0'）
例如，"1*" 可以表示 "11"、"12"、"13"、"14"、"15"、"16"、"17"、"18" 或 "19"
对 "1*" 进行解码，相当于解码该字符串可以表示的任何编码消息
给你一个字符串 s ，由数字和 '*' 字符组成，返回 解码 该字符串的方法 数目
由于答案数目可能非常大，返回10^9 + 7的模
测试链接 : https://leetcode.cn/problems/decode-ways-ii/
题目5
丑数 II
丑数 就是只包含质因数 2、3 或 5 的正整数
默认第1个丑数是1，前几项丑数为:
1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20,
24, 25, 27, 30, 32, 36, 40, 45, 48, 50, 54, 60,
64, 72, 75, 80, 81, 90, 96, 100, 108, 120, 125..
给你一个整数n ，请你找出并返回第n个丑数
比如，n = 37，返回125
测试链接 : https://leetcode.cn/problems/ugly-number-ii/
题目6
最长有效括号
给你一个只包含 '(' 和 ')' 的字符串
找出最长有效（格式正确且连续）括号子串的长度。
测试链接 : https://leetcode.cn/problems/longest-valid-parentheses/
题目7
环绕字符串中唯一的子字符串
定义字符串 base 为一个 "abcdefghijklmnopqrstuvwxyz" 无限环绕的字符串
所以 base 看起来是这样的：
"..zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd.."
给你一个字符串 s ，请你统计并返回 s 中有多少 不同、非空子串 也在 base 中出现
测试链接 : https://leetcode.cn/problems/unique-substrings-in-wraparound-string/
题目8
不同的子序列 II
给定一个字符串 s，计算 s 的 不同非空子序列 的个数
因为结果可能很大，所以返回答案需要对 10^9 + 7 取余
字符串的 子序列 是经由原字符串删除一些（也可能不删除）
字符但不改变剩余字符相对位置的一个新字符串
例如，"ace" 是 "abcde" 的一个子序列，但 "aec" 不是
测试链接 : https://leetcode.cn/problems/distinct-subsequences-ii/2026.05.19 10:41:00
尚同
2026.05.21 11:15:00
尚同
2026.05.24 18:46:00
算法讲解067【必备】从递归入手二维动态规划
1、前置知识
讲解038-经典递归过程解析、讲解066-从递归入手一维动态规划
本节课：
讲解从递归到二维动态规划的过程
讲解二维动态规划的空间压缩技巧
讲解哪些递归不适合或者说没有必要改成动态规划
下节课：直接从动态规划的定义入手，来见识更多二维动态规划问题
注意：
二维动态规划问题非常多，不仅讲解067、讲解068涉及，整个系列课程会大量涉及
【必备】课程后续会讲背包dp、区间dp、状压dp等等，依然包含大量二维动态规划问题
2、内容
二维动态规划的核心，可以先从递归尝试的可变参数数量来理解。
如果一个递归的返回值只由 1 个可变参数完全决定，那么通常可以整理成一维动态规划；
如果一个递归的返回值只由 2 个可变参数完全决定，那么通常可以整理成二维动态规划。
这里的关键不是“题目看起来像几维”，而是“状态到底需要几个可变参数才能完整描述后续过程”。
（1）从递归到动态规划的一般流程
不管是一维、二维，还是更高维的动态规划，整体思路通常都一致：
- 先写出尝试递归，明确每个状态的含义。
- 再改成记忆化搜索，也就是从顶到底的动态规划。
- 如果还需要进一步整理，再写成严格位置依赖的动态规划，也就是从底到顶的填表过程。
- 最后根据依赖关系继续做空间压缩，必要时也可以继续优化时间枚举。
这个过程的本质，是把重复计算变成状态缓存，把递归中的“展开过程”变成“表格中的填表过程”。
（2）动态规划表的规模与时间复杂度
动态规划表的大小，通常等于每个可变参数的取值可能数相乘。
因此，判断一个动态规划是否合适，不能只看状态数，还要看每个格子里要做多少额外枚举。
（3）二维动态规划的关键工作
二维动态规划真正难的地方，不是“写出二维表”，而是“整理格子之间的依赖关系”。
通常需要先通过画图建立空间感，明确当前格子依赖哪些前置格子，再决定填表顺序。
一般原则是：先填依赖少、条件简单的格子，再逐步填到依赖更多、状态更复杂的格子。
只要依赖关系理清楚，二维动态规划就能稳定地从底到顶完成。
（4）空间压缩的基本思路
二维动态规划的空间压缩，原理并不神秘，核心就是只保留当前计算真正需要的那些历史状态。
不同题目的依赖结构不一样，所以空间压缩不能机械套模板，必须先看清楚当前状态到底依赖哪几行、哪几列、或者哪几个方向的数据。
画图整理依赖关系，往往是空间压缩能否顺利实现的前提。
（5）什么样的递归适合改成动态规划
能改成动态规划的递归，通常有一个统一特征：
原因在于，动态规划状态必须能稳定地表示“之前的决策过程对后续过程的影响”。
如果状态本身过于复杂，比如需要携带整条路径，那就意味着状态表达成本太高，通常不适合或者没有必要强行改成动态规划。
题目2就是在说明这一点：有些递归虽然能写出来，但它并不适合转成典型的动态规划状态。
所以，做动态规划时要优先寻找满足下面两个条件的递归：
- 可变参数类型尽量简单，最好不比
int更复杂。 - 这些可变参数必须能够完全决定返回值。
只有满足这两个条件，才能保证当前状态真正代表了之前决策对后续过程的全部影响，再去改写动态规划才是合理的。
（6）写递归时的一个常用习惯
不管几维动态规划，很多时候都应该尽量从递归定义出发，而不是一上来就硬想边界和转移方程。
这样做的好处是，很多边界讨论可以提前被递归定义自然吸收，后续填表时也更顺手。
不过，这种写法需要一定经验，尤其是对状态含义和依赖关系的预判能力。
3、题目
题目1
最小路径和
给定一个包含非负整数的 m x n 网格 grid
请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
测试链接 : https://leetcode.cn/problems/minimum-path-sum/
题目2
单词搜索（无法改成动态规划）
给定一个 m x n 二维字符网格 board 和一个字符串单词 word
如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成
其中"相邻"单元格是那些水平相邻或垂直相邻的单元格
同一个单元格内的字母不允许被重复使用
测试链接 : https://leetcode.cn/problems/word-search/
题目3
最长公共子序列
给定两个字符串text1和text2
返回这两个字符串的最长 公共子序列 的长度
如果不存在公共子序列，返回0
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列
测试链接 : https://leetcode.cn/problems/longest-common-subsequence/
题目4
最长回文子序列
给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度
测试链接 : https://leetcode.cn/problems/longest-palindromic-subsequence/
题目5
节点数为n高度不大于m的二叉树个数
现在有n个节点，计算出有多少个不同结构的二叉树
满足节点个数为n且树的高度不超过m的方案
因为答案很大，所以答案需要模上1000000007后输出
测试链接 : https://www.nowcoder.com/practice/aaefe5896cce4204b276e213e725f3ea
题目6
矩阵中的最长递增路径
给定一个 m x n 整数矩阵 matrix ，找出其中 最长递增路径 的长度
对于每个单元格，你可以往上，下，左，右四个方向移动
不能在对角线方向上移动或移动到边界外（即不允许环绕）
测试链接 : https://leetcode.cn/problems/longest-increasing-path-in-a-matrix/2026.05.25 14:58:00
尚同
2026.05.26 14:30:00
算法讲解068【必备】见识更多二维动态规划题目
1、前置知识
前置知识:
讲解067-从递归入手二维动态规划
本节课不再从递归入手，而是直接从动态规划的定义入手，来见识更多二维动态规划问题
本节课包含一些 比较巧妙的尝试思路
注意：
二维动态规划问题非常多，不仅讲解067、讲解068涉及，整个系列课程会大量涉及
【必备】课程后续会讲背包dp、区间dp、状压dp等等，依然包含大量二维动态规划问题2、题目
题目1
不同的子序列
给你两个字符串s和t
统计在s的所有子序列中
有多少个子序列等于t
测试链接 : https://leetcode.cn/problems/distinct-subsequences/
牛客；https://www.nowcoder.com/practice/ed2923e49d3d495f8321aa46ade9f873
题目2
编辑距离
给你两个单词 word1 和 word2
请返回将 word1 转换成 word2 所使用的最少代价
你可以对一个单词进行如下三种操作：
插入一个字符，代价a
删除一个字符，代价b
替换一个字符，代价c
测试链接 : https://leetcode.cn/problems/edit-distance/
牛客：https://www.nowcoder.com/practice/81d7738f954242e5ade5e65ec40e5027
注意：
测试里说的题意，只是编辑距离问题的一种情况，请掌握完整的编辑距离问题
题目3
交错字符串
给定三个字符串 s1、s2、s3
请帮忙验证s3是否由s1和s2交错组成
测试链接 : https://leetcode.cn/problems/interleaving-string/
题目4
有效涂色问题
给定n、m两个参数
一共有n个格子，每个格子可以涂上一种颜色，颜色在m种里选
当涂满n个格子，并且m种颜色都使用了，叫一种有效方法
求一共有多少种有效的涂色方法
1 <= n, m <= 5000
结果比较大请 % 1000000007 之后返回
对数器验证
题目5
删除至少几个字符可以变成另一个字符串的子串
给定两个字符串s1和s2
返回s1至少删除多少字符可以成为s2的子串
对数器验证3、代码记录
3.1 不同的子序列代码实现
1、图解：
（1） gemini图解：
（2） gpt图解：
（3）手写图解：
cpp
3.2 编辑距离代码实现
1、大致题意：
给你两个单词 word1 和 word2，和三个整数 a、b、c，分别表示插入一个字符、删除一个字符和替换一个字符的代价。请返回将 word1 转换成 word2 所使用的最少代价
2、代码实现
（1）方法一：从递归入手，优化为记忆化搜索
cpp
#include <iostream>
#include <string>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1005;
int dp[N][N];
/**
* @brief 递归计算编辑距离 (带记忆化搜索)
*
* @param s1 字符串1
* @param s2 字符串2
* @param i 当前处理到 s1 的第 i 个字符（1-based）
* @param j 当前处理到 s2 的第 j 个字符（1-based）
* @param a 在 s1 中插入1个字符的代价
* @param b 在 s1 中删除1个字符的代价
* @param c 在 s1 中替换1个字符的代价
* @return int 返回将 s1[0..i-1] 转换为 s2[0..j-1] 的最小代价
*/
int editDistance(const string& s1, const string& s2, int i, int j, int a, int b, int c) {
// 如果已经计算过，直接返回记忆化的结果
if (dp[i][j] != -1) {
return dp[i][j];
}
// 边界情况：s1为空，只能不断进行插入操作来匹配s2
if (i == 0) {
return j * a;
}
// 边界情况：s2为空，只能不断进行删除操作来匹配s2
else if (j == 0) {
return i * b;
}
int ans;
// 如果当前末尾字符相等，则不需要任何操作，代价等于前缀的最小编辑距离
if (s1[i - 1] == s2[j - 1]) {
ans = editDistance(s1, s2, i - 1, j - 1, a, b, c);
} else {
// 否则取插入、删除、替换三种操作中的最小值
// 1. 删除 s1 的最后一个字符，代价递增 b
int cost_delete = editDistance(s1, s2, i - 1, j, a, b, c) + b;
// 2. 在 s1 后面插入一个与 s2 最后一个字符匹配的字符，代价递增 a
int cost_insert = editDistance(s1, s2, i, j - 1, a, b, c) + a;
// 3. 将 s1 的最后一个字符替换为 s2 的最后一个字符，代价递增 c
int cost_replace = editDistance(s1, s2, i - 1, j - 1, a, b, c) + c;
ans = min({cost_delete, cost_insert, cost_replace});
}
// 将结果记录到 DP 数组中，实现记忆化
dp[i][j] = ans;
return ans;
}
int main() {
// 优化标准输入输出流性能
ios_base::sync_with_stdio(false);
cin.tie(NULL);
string word1, word2;
int a, b, c;
// ACM模式通用的多组数据读取 (利用 EOF 结束)
while (cin >> word1 >> word2 >> a >> b >> c) {
// 初始化 dp 数组为 -1，表示所有状态均暂未计算
memset(dp, -1, sizeof(dp));
// 调用递归函数计算 word1 到 word2 的最小编辑距离
int result = editDistance(word1, word2, word1.size(), word2.size(), a, b, c);
// 输出当前用例的最终代价
cout << result << "\n";
}
return 0;
}
// 测试用例：
// 输入：
// abc def 1 1 1
// 输出：
// 3（2）二维动态规划版本
cpp
#include <algorithm>
#include <cstring>
#include <iostream>
#include <string>
using namespace std;
const int N = 1005;
int dp[N][N];
void editDistance(const string& word1, const string& word2, int a, int b, int c) {
int n = word1.size();
int m = word2.size();
// dp[i][j] 表示 word1[0..i-1] 转换为 word2[0..j-1] 的最小代价
memset(dp, 0, sizeof(dp));
// 边界条件初始化
// word2 为空时，只能通过删除 word1 的字符来转换
for (int i = 1; i <= n; ++i) { dp[i][0] = i * b; }
// word1 为空时，只能通过插入新字符来转换成 word2
for (int j = 1; j <= m; ++j) { dp[0][j] = j * a; }
// 状态转移
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (word1[i - 1] == word2[j - 1]) {
// 若当前字符相同，不需要任何操作代价
dp[i][j] = dp[i - 1][j - 1];
} else {
// 取插入、删除、替换操作的最小值
// dp[i-1][j] + b : 删除操作
// dp[i][j-1] + a : 插入操作
// dp[i-1][j-1] + c : 替换操作
dp[i][j] =
min({dp[i - 1][j] + b, dp[i][j - 1] + a, dp[i - 1][j - 1] + c});
}
}
}
}
int main() {
// 优化标准输入输出流性能
ios_base::sync_with_stdio(false);
cin.tie(NULL);
string word1, word2;
int a, b, c;
// ACM模式通用的多组数据读取
while (cin >> word1 >> word2 >> a >> b >> c) {
editDistance(word1, word2, a, b, c);
cout << dp[word1.size()][word2.size()] << "\n";
}
return 0;
}（3）一维动态规划版本（空间压缩）
cpp
#include <algorithm>
#include <cstring>
#include <iostream>
#include <string>
using namespace std;
const int N = 1005;
int dp[N];
void editDistance(const string& word1, const string& word2, int a, int b,
int c) {
int n = word1.size(), m = word2.size();
// 仅使用一维数组来保存当前正在计算的行的状态
memset(dp, 0, sizeof(dp));
// 初始化第0行 (word1 为空，只能用插入操作构建 word2)
for (int j = 1; j <= m; ++j) { dp[j] = j * a; }
// 逐行更新
for (int i = 1; i <= n; ++i) {
// left_up 相当于二维DP中的 dp[i-1][j-1]
int left_up = dp[0];
// 当前行的 dp[0] 表示 word2 为空，只能对 word1 执行删除操作
dp[0] = i * b;
for (int j = 1; j <= m; ++j) {
// 暂时保存旧的 dp[j]，它对于下一个 j (即 j+1) 来说就是左上角的值
int temp = dp[j];
if (word1[i - 1] == word2[j - 1]) {
dp[j] = left_up;
} else {
// 取三种操作最小代价
// dp[j] 在更新前对应 dp[i-1][j] (删除)
// dp[j-1] 对应 dp[i][j-1] (插入)
// left_up 对应 dp[i-1][j-1] (替换)
dp[j] = min({dp[j] + b, dp[j - 1] + a, left_up + c});
}
// 将旧的 dp[j] 传给 left_up，供下个字符(j+1)匹配时作为左上角的值使用
left_up = temp;
}
}
}
int main() {
// 优化标准输入输出流性能
ios_base::sync_with_stdio(false);
cin.tie(NULL);
string word1, word2;
int a, b, c;
// ACM模式通用的多组数据读取
while (cin >> word1 >> word2 >> a >> b >> c) {
editDistance(word1, word2, a, b, c);
cout << dp[word2.size()] << "\n";
}
return 0;
}3.3 题目四代码实现
cpp
/*
有效涂色问题
给定n、m两个参数
一共有n个格子，每个格子可以涂上一种颜色，颜色在m种里选
当涂满n个格子，并且m种颜色都使用了，叫一种有效方法
求一共有多少种有效的涂色方法
1 <= n, m <= 5000
结果比较大请 % 1000000007 之后返回
对数器验证
*/
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <chrono> // 添加 chrono 库用于精确计时
#include <iomanip> // 格式化输出
using namespace std;
const int K = 5005, MOD = 1e9 + 7;
// dp2[i][j] 表明在 i 个格子中填满 j 种颜色的方案数量
int dp1[K][K];
int dp2[K][K];
int dp3[K];
// 回溯暴力算法
int path[K];
bool isUsed[K];
int sz;
int dfs(int n, int m, int i) {
if (i == n) {
int cnt = 0;
memset(isUsed, false, sizeof(isUsed));
for (int t = 0; t < n; t++) {
if (!isUsed[path[t]]) {
cnt++;
isUsed[path[t]] = true;
}
}
return cnt == m;
}
int ans = 0;
for (int t = 1; t <= m; t++) {
path[sz++] = t;
ans += dfs(n, m, i + 1);
sz--;
}
return ans;
}
int f1(int n, int m) {
sz = 0;
return dfs(n, m, 0);
}
// 动态规划：时间复杂度 O(n*m)，二维数组
int f2(int n, int m) {
// 必须满足颜色数不超过格子数才能实现全覆盖
if (m > n || m == 0 || n == 0) return 0;
// 优化初始化：按所需区域清理，防止超大常数时间的 memset
for (int i = 0; i <= n; i++) {
memset(dp2[i], 0, (m + 1) * sizeof(int));
}
dp2[1][1] = m; // 初始化：1个格子涂1种颜色，共有m种选法
for (int i = 2; i <= n; i++) {
dp2[i][1] = m; // i个格子涂1种颜色，依然只有m种选法（所有格子同色）
for (int j = 2; j <= m; j++) {
// 1. 第 i 个格子涂以前用过的 j 种颜色之一：dp2[i - 1][j] * j
// 2. 第 i 个格子涂一种新颜色，从剩余 m - (j - 1) 种里选：dp2[i - 1][j - 1]* (m - j + 1)
dp2[i][j] = ((long long)dp2[i - 1][j] * j % MOD +
(long long)dp2[i - 1][j - 1] * (m - j + 1) % MOD) % MOD;
}
}
return dp2[n][m];
}
// 动态规划：时间复杂度 O(n*m)，空间压缩到一维
int f3(int n, int m) {
if (m > n || m == 0 || n == 0) return 0;
// 优化初始化：由于数组只有 O(m) 的规模，极极快完成清理
memset(dp3, 0, (m + 1) * sizeof(int));
dp3[1] = m; // 初始化第1行：只有一个格子时，用1种颜色有m种方案
for (int i = 2; i <= n; i++) {
// 逆序更新防止当前层的数据覆盖了下一项计算依赖的上一层数据
for (int j = m; j >= 2; j--) {
dp3[j] = ((long long)dp3[j] * j % MOD +
(long long)dp3[j - 1] * (m - j + 1) % MOD) % MOD;
}
// 注意 dp3[1] 在每一层中含义为 i 个格子涂 1 种颜色，永远等于 m，故无需更新
}
return dp3[m];
}
// 计时辅助函数：测量函数执行时间
template<typename Func>
double measureTime(Func func, int n, int m, int& result) {
auto start = chrono::high_resolution_clock::now();
result = func(n, m);
auto end = chrono::high_resolution_clock::now();
chrono::duration<double, milli> duration = end - start;
return duration.count();
}
// 测试和对数器验证主函数
int main() {
srand(time(NULL));
ios::sync_with_stdio(false);
cin.tie(NULL);
cout << "================= 开始算法正确性测试 =================" << endl;
int N = 10, M = 10;
int testTimes = 50;
bool success = true;
for (int i = 0; i < testTimes; i++) {
int n = rand() % N + 1;
int m = rand() % M + 1;
int ans1 = f1(n, m); // 暴力
int ans2 = f2(n, m); // 普通DP
int ans3 = f3(n, m); // 数组压缩DP
if (ans1 != ans2 || ans2 != ans3) {
cout << "[测试失败] n: " << n << ", m: " << m << endl;
cout << "f1(暴力): " << ans1 << ", f2(2D DP): " << ans2 << ", f3(1D DP): " << ans3 << endl;
success = false;
break;
}
}
if (success) {
cout << "通过 " << testTimes << " 次随机数据一致性校验！所有算法输出结果相符。" << endl;
}
cout << "\n================= 执行时间对比 (小数据) =================" << endl;
int small_n = 12, small_m = 6;
int res1, res2, res3;
double t1 = measureTime(f1, small_n, small_m, res1);
double t2 = measureTime(f2, small_n, small_m, res2);
double t3 = measureTime(f3, small_n, small_m, res3);
cout << "测试规模 N=" << small_n << ", M=" << small_m << ":" << endl;
cout << "f1(回溯暴力) 耗时: " << fixed << setprecision(4) << t1 << " ms, \t结果: " << res1 << endl;
cout << "f2(2D 动规) 耗时: " << fixed << setprecision(4) << t2 << " ms, \t结果: " << res2 << endl;
cout << "f3(空间压缩) 耗时: " << fixed << setprecision(4) << t3 << " ms, \t结果: " << res3 << endl;
cout << "\n================= 执行时间对比 (大数据) =================" << endl;
int large_n = 5000, large_m = 2500;
// 暴力法无法计算此规模，直接略过
double time2 = measureTime(f2, large_n, large_m, res2);
double time3 = measureTime(f3, large_n, large_m, res3);
cout << "测试规模 N=" << large_n << ", M=" << large_m << ":" << endl;
cout << "f2(2D 动规) 耗时: " << fixed << setprecision(4) << time2 << " ms, \t结果: " << res2 << endl;
cout << "f3(空间压缩) 耗时: " << fixed << setprecision(4) << time3 << " ms, \t结果: " << res3 << endl;
return 0;
}2026.05.27 20:48:00
尚同
2026.05.28 11:45:00
尚同
2026.06.09 18:30:00
算法讲解069【必备】从递归入手三维动态规划
1、前置知识
前置知识:
讲解068-从递归入手二维动态规划
从讲解066开始都是动态规划大专题，建议从头开始学习会比较容易理解
从递归到三维动态规划，包含多维费用背包
严格位置依赖的三维动态规划
三维动态规划的空间压缩
注意：
多维费用背包问题就是很普通的动态规划
但是【必备】课程里还会安排背包dp的内容，那时候会把其他几种背包问题做汇总讲述2、内容
尝试函数有1个可变参数可以完全决定返回值，进而可以改出1维动态规划表的实现
同理
尝试函数有2个可变参数可以完全决定返回值，那么就可以改出2维动态规划的实现
同理
尝试函数有3个可变参数可以完全决定返回值，那么就可以改出3维动态规划的实现
大体过程都是：
写出尝试递归
记忆化搜索(从顶到底的动态规划)
严格位置依赖的动态规划(从底到顶的动态规划)
空间、时间的更多优化
原理完全一样，可以参考讲解067 那么直接看题目吧！3、题目
题目1
一和零(多维费用背包)
给你一个二进制字符串数组 strs 和两个整数 m 和 n
请你找出并返回 strs 的最大子集的长度
该子集中 最多 有 m 个 0 和 n 个 1
如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集
测试链接 : https://leetcode.cn/problems/ones-and-zeroes/
题目2
盈利计划(多维费用背包)
集团里有 n 名员工，他们可以完成各种各样的工作创造利润
第 i 种工作会产生 profit[i] 的利润，它要求 group[i] 名成员共同参与
如果成员参与了其中一项工作，就不能参与另一项工作
工作的任何至少产生 minProfit 利润的子集称为 盈利计划
并且工作的成员总数最多为 n
有多少种计划可以选择？因为答案很大，所以 返回结果模 10^9 + 7 的值。
测试链接 : https://leetcode.cn/problems/profitable-schemes/
题目3
骑士在棋盘上的概率
n * n的国际象棋棋盘上，一个骑士从单元格(row, col)开始，并尝试进行 k 次移动
行和列从0开始，所以左上单元格是 (0,0)，右下单元格是 (n-1, n-1)
象棋骑士有8种可能的走法。每次移动在基本方向上是两个单元格，然后在正交方向上是一个单元格
每次骑士要移动时，它都会随机从8种可能的移动中选择一种，然后移动到那里
骑士继续移动，直到它走了 k 步或离开了棋盘
返回 骑士在棋盘停止移动后仍留在棋盘上的概率
测试链接 : https://leetcode.cn/problems/knight-probability-in-chessboard/
题目4
矩阵中和能被 K 整除的路径
给一个下标从0开始的 n * m 整数矩阵 grid 和一个整数 k
从起点(0,0)出发，每步只能往下或者往右，你想要到达终点(m-1, n-1)
请你返回路径和能被 k 整除的路径数目
由于答案可能很大，返回答案对10^9+7取余的结果
测试链接 :
https://leetcode.cn/problems/paths-in-matrix-whose-sum-is-divisible-by-k/
题目5
扰乱字符串
使用下面描述的算法可以扰乱字符串 s 得到字符串 t ：
步骤1 : 如果字符串的长度为 1 ，算法停止
步骤2 : 如果字符串的长度 > 1 ，执行下述步骤：
在一个随机下标处将字符串分割成两个非空的子字符串
已知字符串s，则可以将其分成两个子字符串x和y且满足s=x+y
可以决定是要 交换两个子字符串 还是要 保持这两个子字符串的顺序不变
即s可能是 s = x + y 或者 s = y + x
在x和y这两个子字符串上继续从步骤1开始递归执行此算法
给你两个 长度相等 的字符串 s1 和 s2，判断 s2 是否是 s1 的扰乱字符串
如果是，返回true ；否则，返回false
测试链接 : https://leetcode.cn/problems/scramble-string/杂
画图：所有图算法进行对比，包括时间复杂度、空间复杂度、适用条件、核心思想、代码模板等维度的对比总结。
在线Debug 时间限制（2s）
https://www.acwing.com/problem/content/4903/
相似题目
https://leetcode.cn/problems/trapping-rain-water/
https://leetcode.cn/problems/container-with-most-water/