Leetcode动态规划模板
文章目录
0 前言
路径 | 基本要素 | 说明 |
|---|---|---|
核心基础 | 穷举法 | 需“聪明”穷举 |
存在问题 | 重叠子问题 | 有众多相同子问题(eg.多个f(18))，需记录 |
具备特点 | 最优子结构 | 原问题的解包含子问题的解 |
状态转移思维模式 | 自顶向下(推荐) | 当前状态如何由前一个状态推出 |
目前所遇动态规划问题一般形式包括
形式 | 状态转移方程一般式（滚动数组） | 初始化 | 遍历顺序 |
|---|---|---|---|
求最值 | dpj = max(dpj, dp[j - weighti] + vali) | dp0 = 0 | 物品和背包可颠倒但先物品后容量耗时低 |
求组合数 | dpj = dpj + dp[j - weighti] | dp0 = 1 | 先物品，后背包容量 |
求排列数 | dpj = dpj + dp[j - weighti] | dp0 = 1 | 先背包容量，后物品 |
- 这里为什么变动一下遍历顺序，就从求组合数变成求排列数了呢？因为先遍历物品后遍历背包容量，隐含了我在《Leetcode回溯法四板一解模板》中提到的对待组合问题的**
first**索引技巧，不用它则求解为排列问题（不得不说动态规划和回溯法面对同类型题，特定领域技巧是相通的）详情可以点击了解. - 为什么在不要求遍历顺序的问题上，更推荐先遍历物品，再遍历背包容量呢？因为组合比排列有更少的搜索量！
背包集合 | 代码特点 | 原因 | for外遍历顺序 |
|---|---|---|---|
0-1背包 | 背包容量for循环j--降序 | 不论容量多少最多装1次，避免累加 | 组合→先物品后背包 排列→先背包后物品 |
完全背包 | 背包容量for循环j++升序 | 容量越多最多可方便无限累加 | 组合→先物品后背包 排列→先背包后物品 |
1 解题思考模式
1.1 能不能用动态规划做？
由于面试解题没有时间进行数学验证，因此需要训练一些基本feeling，满足feeling即可果断尝试，十拿九稳！
if能穷举出所有解，回溯法能不能搜索出所有解？if是,then回溯可得正确答案- 原问题是否包含多个
相同子问题？if是,then回溯可能会超时 (力扣：编辑距离) - 子问题的解是否相互独立？，最起码
独立可满足最优子结构性质——独立：总高考分 = 语文成绩 + 数学成绩 + …，其中语文成绩与数学成绩无关——相关：总高考分 = 语文成绩 + 数学成绩 + …，其中语文成绩与数学成绩成反比关系，导致无法同时最优 - 满足以上条件可用动态规划做
1.2 怎么用动态规划做？（七步走）
顺序 | 思考步骤 | 解释/例子 |
|---|---|---|
1 | 有什么状态？ | 容量，累计和，金额等 |
2 | 有什么选择？ | 该物品装与不装，该数值是否累计，该硬币是否添加等 |
3 | dpj数组含义是什么？ | 索引j表状态(eg.容量)，返回值dpj是题目的解 |
4 | 如何定义状态转移？ | 任意状态由前状态经过怎样的选择转移达到(自顶向下) |
5 | 如何初始化dp数组？ | 结合状态转移初始化，eg.max初始全0，求和dp0=1，有负数初始INT_MIN |
6 | for外遍历顺序？ | 求最值推荐先物品后背包，求组合先物品后背包，求排列先背包后物品 |
7 | for内遍历顺序？ | 有状态压缩则背包容量for内降序，无状态压缩则升序 |
2 动态规划模板
2.1 通用模板
// 1.通用初始化
vector<int> dp(容量 + 1, base case1);
// 2.边界初始化
dp[0][0][...] = base case2
// 3.状态转移
for 状态1的个数
for 状态2的个数
for ...
dp[状态1][状态2][...] = 求最值 or 求和(选择1, 选择2，...)2.2 背包模板
以下模板均以状态压缩后的滚动数组为例
2.2.1 01背包模板
每个物品有装1次，或不装两个选择
1 最值问题
状态转移方程：背包容量下的最值 = max(不装物品i最值, 装物品i的最值)，最小反之
- 物品价值
全部非负
// 1.通用dp初始化
vector<int> dp(背包容量 + 1, 0);
for (int i = 0; i < 物品总数; i++)
for (int j = 背包容量; j >= 物品i的重量; j--) {
// 3.背包容量下的最值 = max(不装物品i最值, 装物品i的最值)
dp[j] = max(dp[j], dp[j - 物品i的重量] + 物品i的价值);
}
return dp[背包容量];- 物品价值
存在负数（初始化INT_MIN或INT_MAX+for内判断）
// 1.通用dp初始化
vector<int> dp(背包容量 + 1, INT_MIN);
// 2.边界dp初始化
dp[0] = 0;
for (int i = 0; i < 物品总数; i++)
for (int j = 背包容量; j >= 物品i的重量; j--) {
if (dp[i - 物品i的重量] == INT_MIN) continue; // 因为不能有INT_MIN + 常数
// 3.背包容量下的最值 = max(不装物品i最值, 装物品i的最值)
dp[j] = max(dp[j], dp[j - 物品i的重量] + 物品i的价值);
}
return dp[背包容量];2 组合问题
- 返回具体组合数
状态转移方程：总组合数 = 不装物品i的组合数 + 装物品i的组合数
// 1.通用dp初始化
vector<int> dp(背包容量 + 1, 0);
// 2.边界dp初始化
dp[0] = 1; // [关键]：根据状态转移方程，dp[0]须为1
for (int i = 0; i < 物品总数; i++)
for (int j = 背包容量; j >= 物品i的重量; j--) {
// 3.总组合数 = 不装物品i的组合数 + 装物品i的组合数
dp[j] = dp[j] + dp[j - 物品i的重量];
}
return dp[背包容量];- 返回组合的存在还是不存在
状态转移方程：组合是否有 = 不装物品i的组合是否有 || 装物品i的组合是否有
// 1.通用dp初始化
vector<int> dp(背包容量 + 1, false);
// 2.边界dp初始化
dp[0] = true; // [关键]：根据状态转移方程，dp[0]须为true
for (int i = 0; i < 物品总数; i++)
for (int j = 背包容量; j >= 物品i的重量; j--) {
// 3.组合是否有 = 不装物品i的组合是否有 || 装物品i的组合是否有
dp[j] = dp[j] || dp[j - 物品i的重量];
}
return dp[背包容量];3 排列问题
状态转移方程：总排列数 = 不装物品i的排列数 + 装物品i的排列数
// 1.通用dp初始化
vector<int> dp(背包容量 + 1, 0);
// 2.边界dp初始化
dp[0] = 1; // [关键]：根据状态转移方程，dp[0]须为1
for (int j = 1; j <= 背包容量; j++) {
for (int i = 0; i < 物品总数; i++)
// 3.总组合数 = 不装物品i的排列数 + 装物品i的排列数
dp[j] = dp[j] + dp[j - 物品i的重量];
}
return dp[背包容量];2.2.2 完全背包模板
每个物品有装无限次，或不装两个选择
组合问题（背包容量for循环升序）
- 返回具体组合数
状态转移方程：总组合数 = 不装物品i的组合数 + 装物品i的组合数
// 1.通用dp初始化
vector<int> dp(背包容量 + 1, 0);
// 2.边界dp初始化
dp[0] = 1; // [关键]：根据状态转移方程，dp[0]须为1
for (int i = 0; i < 物品总数; i++)
for (int j = 物品i的重量; j <= 背包容量; j++) {
// 3.总组合数 = 不装物品i的组合数 + 装物品i的组合数
dp[j] = dp[j] = dp[j] + dp[j - 物品i的重量];
}
return dp[背包容量];刷题还在继续，持续总结中~
腾讯云开发者
