动态规划算法——简单多状态dp问题统一解题模板线性DP五步法1. 状态表示以i位置结尾拆分多种状态选/不选、持有/不持有、不同颜色2. 状态转移方程根据上一步所有合法状态推导取最值3. 初始化处理边界设置基础值不存在的状态初始化为负无穷4. 填表顺序从左往右多个状态数组同步填写5. 返回值最后位置所有合法状态的最大值/最小值11. 按摩师面试题 17.16 easy题目描述算法思路1. 状态表示对于简单的线性 dp我们可以用「经验 题目要求」来定义状态表示i. 以某个位置为结尾 ii. 以某个位置为起点这里选择以某个位置结尾拆分两种抉择f[i]选择到 i 位置时nums[i] 必选此时的最长预约时长g[i]选择到 i 位置时nums[i] 不选此时的最长预约时长。2. 状态转移方程• 对于f[i]如果nums[i]必选那么i-1位置一定不能选取i-1不选的状态加上当前值。f[i] g[i - 1] nums[i]• 对于g[i]如果nums[i]不选i-1可选可不选取两者最大值。g[i] max(f[i - 1], g[i - 1])3. 初始化无需辅助节点初始化f[0] nums[0]g[0] 0。4. 填表顺序从左往右两个数组一起填。5. 返回值max(f[n - 1], g[n - 1])C代码class Solution { public: int massage(vectorint nums) { // 1. 创建一个 dp 表 // 2. 初始化 // 3. 填表 // 4. 返回值 int n nums.size(); if(n 0) return 0; // 处理边界条件 vectorint f(n); auto g f; f[0] nums[0]; g[0] 0; for(int i 1; i n; i) { f[i] g[i - 1] nums[i]; g[i] max(f[i - 1], g[i - 1]); } return max(f[n - 1], g[n - 1]); } };12. 打家劫舍 IILeetCode 213 medium题目描述算法思路这是「打家劫舍I」的变形。普通打家劫舍是单排本题是环形首尾相连。环形问题转化成两次单排DPa. 偷第一个房屋就不能偷最后一个区间[0, n-2]b. 不偷第一个房屋可以偷最后一个区间[1, n-1]最终答案 两种情况的最大值C代码class Solution { public: int rob(vectorint nums){ int n nums.size(); // 两种情况下的最大值 return max(rob1(nums, 0, n - 2), rob1(nums, 1, n - 1)); } int rob1(vectorint nums, int left, int right){ if(left right) return 0; // 1. 创建 dp 表 // 2. 初始化 // 3. 填表 // 4. 返回结果 int n nums.size(); vectorint f(n); auto g f; f[left] nums[left]; // 初始化 g[left] 0; for(int i left 1; i right; i) { f[i] g[i - 1] nums[i]; g[i] max(f[i - 1], g[i - 1]); } return max(f[right], g[right]); } };13. 删除并获得点数LeetCode 740 medium题目描述算法思路本质是打家劫舍的变形选x则不能选x-1和x1。预处理构建hash数组arr[x]存放所有x数字的总和在arr数组上跑打家劫舍DP。C代码class Solution { public: int deleteAndEarn(vectorint nums) { const int N 10001; // 1. 预处理 int arr[N] { 0 }; for(auto x : nums) arr[x] x; // 2. 在 arr 数组上做一次“打家劫舍”问题 // 创建 dp 表 vectorint f(N); auto g f; // 填表 for(int i 1; i N; i) { f[i] g[i - 1] arr[i]; g[i] max(f[i - 1], g[i - 1]); } // 返回结果 return max(f[N - 1], g[N - 1]); } };14. 粉刷房子LCR 091 medium题目描述算法思路1. 状态表示dp[i][0]粉刷到i位置最后房子刷红色最小花费dp[i][1]粉刷到i位置最后房子刷蓝色最小花费dp[i][2]粉刷到i位置最后房子刷绿色最小花费。2. 状态转移方程相邻房子颜色不能相同dp[i][0] min(dp[i-1][1], dp[i-1][2]) costs[i-1][0]dp[i][1] min(dp[i-1][0], dp[i-1][2]) costs[i-1][1]dp[i][2] min(dp[i-1][0], dp[i-1][1]) costs[i-1][2]3. 初始化增加辅助结点初始值全部为0。4. 填表顺序从左往右三个状态一起填。5. 返回值min(dp[n][0], dp[n][1], dp[n][2])C代码class Solution { public: int minCost(vectorvectorint costs) { // dp[i][j] 第i个房子刷成第j种颜色最小花费 int n costs.size(); vectorvectorint dp(n 1, vectorint(3)); for (int i 1; i n; i) { dp[i][0] min(dp[i - 1][1], dp[i - 1][2]) costs[i - 1][0]; dp[i][1] min(dp[i - 1][0], dp[i - 1][2]) costs[i - 1][1]; dp[i][2] min(dp[i - 1][1], dp[i - 1][0]) costs[i - 1][2]; } return min(dp[n][0], min(dp[n][1], dp[n][2])); } };15. 买卖股票的最佳时机含冷冻期LeetCode 309 medium题目描述算法思路1. 状态表示dp[i][0]第i天结束持有股票买入状态最大利润dp[i][1]第i天结束无股票、可交易最大利润dp[i][2]第i天结束无股票、冷冻期最大利润2. 状态转移方程dp[i][0] max(dp[i-1][0], dp[i-1][1] - prices[i])①前一天就持有②前一天可交易今天买入dp[i][1] max(dp[i-1][1], dp[i-1][2])①前一天可交易②前一天冷冻期今天解冻dp[i][2] dp[i-1][0] prices[i]只能是前一天持有今天卖出3. 初始化dp[0][0] -prices[0];dp[0][1] 0;dp[0][2] 0;4. 填表顺序从左向右三个状态一起填5. 返回值max(dp[n-1][1], dp[n-1][2])C代码class Solution { public: int maxProfit(vectorint prices) { // 1. 创建 dp 表 // 2. 初始化 // 3. 填表 // 4. 返回结果 int n prices.size(); vectorvectorint dp(n, vectorint(3)); dp[0][0] -prices[0]; dp[0][1] 0; dp[0][2] 0; for(int i 1; i n; i) { dp[i][0] max(dp[i - 1][0], dp[i - 1][1] - prices[i]); dp[i][1] max(dp[i - 1][1], dp[i - 1][2]); dp[i][2] dp[i - 1][0] prices[i]; } return max(dp[n - 1][1], dp[n - 1][2]); } };16. 买卖股票的最佳时机含手续费LeetCode 714 medium题目描述算法思路1. 状态表示f[i]第i天结束持有股票买入状态最大利润g[i]第i天结束不持有股票卖出状态最大利润2. 状态转移方程手续费在卖出时扣除f[i] max(f[i-1], g[i-1] - prices[i])①前一天持有②前一天无股票今天买入g[i] max(g[i-1], f[i-1] prices[i] - fee)①前一天无股票②前一天持有今天卖出减去手续费3. 初始化f[0] -prices[0]g[0] 04. 填表顺序从左向右两个状态一起填5. 返回值g[n-1]C代码class Solution { public: int maxProfit(vectorint prices, int fee) { // 1. 创建 dp 表 // 2. 初始化 // 3. 填表 // 4. 返回结果 int n prices.size(); vectorint f(n); auto g f; f[0] -prices[0]; g[0] 0; for(int i 1; i n; i) { f[i] max(f[i - 1], g[i - 1] - prices[i]); g[i] max(g[i - 1], f[i - 1] prices[i] - fee); } return g[n - 1]; } };17. 买卖股票的最佳时机 IIILeetCode 123 hard题目描述提示1 prices.length 1050 prices[i] 105算法思路增加一维交易次数jf[i][j]第i天结束完成j次交易持有股票最大利润g[i][j]第i天结束完成j次交易不持有股票最大利润转移方程f[i][j] max(f[i-1][j], g[i-1][j] - prices[i])①前一天j次交易持有②前一天j次交易无股票今天买入g[i][j] g[i-1][j]前一天j次交易无股票不操作如果j1g[i][j] max(g[i][j], f[i-1][j-1] prices[i])前一天j-1次交易持有今天卖出交易次数1初始化不存在的状态赋值为负无穷0x3f3f3f3ff[0][0] -prices[0]; g[0][0] 0;返回g数组最后一行的最大值0x3f3f3f3f 详解算法题常用无穷大0x3f3f3f3f 是十六进制换算十进制 1061109567✅ 为什么选这个数而不是 INT_MAX(2147483647)1. 足够大但加起来不会立刻溢出INT_MAX 正数 直接整型溢出 → 负数bug。0x3f3f3f3f 0x3f3f3f3f 2122219134仍然小于 int 上限 2147483647最常用在最短路、DPdist[v] min(dist[v], dist[u]w)两个无穷相加不会爆int2. 方便批量初始化数组memset(dp, 0x3f, sizeof(dp)); memset是按字节赋值1字节8bit。int占4字节每个字节填 0x3f4个字节拼起来就是 0x3f3f3f3f。一句话一行memset就能把整个数组全部设成无穷大。如果用INT_MAXmemset没法一次性设置。3. 不会和合法数值冲突大部分题目数据范围远小于 1e90x3f3f3f3f代表“不可到达、无穷远”不会和正常答案混淆。C代码class Solution { public: const int INF 0x3f3f3f; int maxProfit(vectorint prices) { // 1. 创建 dp 表 // 2. 初始化 // 3. 填表 // 4. 返回结果 int n prices.size(); vectorvectorint f(n, vectorint(3, -INF)); auto g f; f[0][0] -prices[0], g[0][0] 0; for(int i 1; i n; i) { for(int j 0; j 3; j) { f[i][j] max(f[i - 1][j], g[i - 1][j] - prices[i]); g[i][j] g[i - 1][j]; if(j 1) // 如果该状态存在 g[i][j] max(g[i][j], f[i - 1][j - 1] prices[i]); } } // 找到最后一行的最大值 int ret 0; for(int j 0; j 3; j) ret max(ret, g[n - 1][j]); return ret; } };18. 买卖股票的最佳时机 IVLeetCode 188 hard题目描述算法思路状态表示• f[i][j]第i天结束完成j笔交易手里有股票的最大收益• g[i][j]第i天结束完成j笔交易手里没有股票的最大收益。状态转移方程f[i][j] max(f[i-1][j], g[i-1][j] - prices[i])g[i][j] max(g[i-1][j], f[i-1][j-1] prices[i])优化最多交易次数不会超过n/2k min(k, n/2)减少计算规模。C代码class Solution { public: const int INF 0x3f3f3f3f; int maxProfit(int k, vectorint prices) { // 处理细节交易上限最多 n/2 int n prices.size(); k min(k, n / 2); vectorvectorint f(n, vectorint(k 1, -INF)); auto g f; f[0][0] -prices[0]; g[0][0] 0; for(int i 1; i n; i){ for(int j 0; j k; j){ f[i][j] max(f[i-1][j], g[i-1][j] - prices[i]); g[i][j] g[i-1][j]; if(j 1){ g[i][j] max(g[i][j], f[i-1][j-1] prices[i]); } } } int ans 0; for(int j 0; j k; j) ans max(ans, g[n-1][j]); return ans; } };核心知识点总结1. 基础模型打家劫舍选/不选二状态DP状态f[i]必选ig[i]不选i转移f[i] g[i-1]val[i]g[i]max(f[i-1],g[i-1])变种环形打家劫舍II拆成两次线性DP分别去掉首/尾删除并获得点数数值映射数组转化打家劫舍2. 多状态DP多个并行状态粉刷房子3种颜色相邻不能相同求最小花费状态是3个股票系列基础2状态持有 / 不持有冷冻期增加冷冻期状态一共3种带交易次数限制增加一维j代表交易次数三维DP(天数,次数,持有状态)3. 通用解题套路五步法万能模板1) 状态定义以i结尾拆分所有互斥的状态选/不选、持有/无、颜色2) 转移方程分析当前状态可以从前面哪些合法状态转移而来取max/min3) 初始化合法基础状态赋值不可能的状态赋值负无穷求最大值时辅助结点技巧在最前面虚拟下标简化边界判断4) 填表顺序从左往右多个状态数组同步循环更新5) 返回结果最后位置所有合法状态的最值4. 易错点1) 环形DP不能直接一次性计算首尾互斥必须拆分两次线性DP取max2) 股票DP卖出才增加交易次数买入不增加次数3) 负无穷0x3f3f3f3f防止INT_MIN加法溢出4) 下标映射题目数组下标和dp表下标要区分不要错位动态规划算法——子数组系列核心模板线性DP五步法1. 状态表示一般定义 dp[i] 表示以i位置结尾的目标量最常用2. 状态转移方程根据最近一步划分情况推导3. 初始化增设辅助结点处理下标越界保证填表逻辑正确4. 填表顺序从左往右依赖前面状态5. 返回值看题目可能返回dp数组最大值 / dp[n] / dp数组总和19. 最大子数组和LeetCode 53 medium题目描述算法思路1. 状态表示dp[i]以 i 位置元素结尾的所有子数组中和的最大值。2. 状态转移方程子数组分两种情况长度为1dp[i] nums[i]长度1dp[i] dp[i-1] nums[i]dp[i] max(nums[i], dp[i-1]nums[i])3. 初始化前面增加辅助结点dp[0]0。4. 填表顺序从左往右5. 返回值dp表里面的最大值C代码class Solution { public: int maxSubArray(vectorint nums) { int n nums.size(); vectorint dp(n 1); int ret INT_MIN; for(int i 1; i n; i) { dp[i] max(nums[i - 1], dp[i - 1] nums[i - 1]); ret max(ret, dp[i]); } return ret; } };20. 环形子数组的最大和LeetCode 918 medium题目描述算法思路两种情况1最大子数组在数组内部fmax直接用最大子数组和2最大子数组跨首尾总和 sum 减去最小子数组和 gmin边界特例数组全部是负数时sum gmin此时直接返回数组最大值fmax1. 状态表示g[i]以 i 做结尾的所有子数组中和的最小值。2. 状态转移方程g[i] min(nums[i], g[i-1]nums[i])3. 初始化辅助结点 g[0]04. 填表顺序从左往右5. 返回值sum gmin ? fmax : max(fmax, sum - gmin)C代码class Solution { public: int maxSubarraySumCircular(vectorint nums) { int n nums.size(); vectorint f(n 1), g(n 1); int fmax INT_MIN, gmin INT_MAX, sum 0; for(int i 1; i n; i) { int x nums[i - 1]; f[i] max(x, x f[i - 1]); fmax max(fmax, f[i]); g[i] min(x, x g[i - 1]); gmin min(gmin, g[i]); sum x; } return sum gmin ? fmax : max(fmax, sum - gmin); } };21. 乘积最大子数组LeetCode 152 medium题目描述算法思路⚠️ 乘积和求和不一样负数 × 负数 变正数。只存最大值不够需要同时保存「以i结尾最大乘积、最小乘积」1. 状态表示f[i]以i结尾的所有子数组的最大乘积g[i]以i结尾的所有子数组的最小乘积2. 状态转移方程f[i] max(nums[i], max(nums[i]*f[i-1], nums[i]*g[i-1]))g[i] min(nums[i], min(nums[i]*f[i-1], nums[i]*g[i-1]))3. 初始化辅助结点 f[0]g[0]14. 填表顺序从左往右两个数组一起填5. 返回值f表中的最大值C代码class Solution { public: int maxProduct(vectorint nums) { int n nums.size(); vectorint f(n 1), g(n 1); f[0] g[0] 1; int ret INT_MIN; for(int i 1; i n; i) { int x nums[i - 1], y f[i - 1] * nums[i - 1], z g[i - 1] * nums[i - 1]; f[i] max(x, max(y, z)); g[i] min(x, min(y, z)); ret max(ret, f[i]); } return ret; } };22. 乘积为正数的最长子数组LeetCode 1567 medium题目描述算法思路1. 状态表示f[i]以i结尾乘积为正数的最长子数组长度g[i]以i结尾乘积为负数的最长子数组长度2. 状态转移nums[i]0f[i]0g[i]0nums[i]0f[i]f[i-1]1g[i] g[i-1]0 ? 0 : g[i-1]1nums[i]0f[i] g[i-1]0 ? 0 : g[i-1]1g[i] f[i-1]13. 初始化f[0]g[0]04. 填表顺序从左往右两表一起填5. 返回值f数组的最大值C代码class Solution { public: int getMaxLen(vectorint nums) { int n nums.size(); vectorint f(n 1), g(n 1); int ret INT_MIN; for(int i 1; i n; i) { if(nums[i - 1] 0) { f[i] f[i - 1] 1; g[i] g[i - 1] 0 ? 0 : g[i - 1] 1; } else if(nums[i - 1] 0) { f[i] g[i - 1] 0 ? 0 : g[i - 1] 1; g[i] f[i - 1] 1; } else { f[i] 0; g[i] 0; } ret max(ret, f[i]); } return ret; } };23. 等差数列划分LeetCode 413 medium题目描述算法思路1. 状态表示dp[i]必须以i位置元素结尾的等差数列有多少种。2. 状态转移方程判断 nums[i-2], nums[i-1], nums[i] 是否等差不是等差数列dp[i]0是等差数列dp[i] dp[i-1] 13. 初始化dp[0]0dp[1]0前两个元素无法构成等差数列4. 填表顺序从左往右5. 返回值dp数组全部元素之和C代码class Solution { public: int numberOfArithmeticSlices(vectorint nums) { int n nums.size(); vectorint dp(n); int sum 0; for(int i 2; i n; i) { dp[i] nums[i] - nums[i - 1] nums[i - 1] - nums[i - 2] ? dp[i - 1] 1 : 0; sum dp[i]; } return sum; } };24. 最长湍流子数组LeetCode 978 medium题目描述提示1 arr.length 4 * 1040 arr[i] 109算法思路湍流需要记录结尾状态是上升/下降双dp数组1. 状态表示f[i]以i结尾最后一步是上升的最长湍流子数组长度g[i]以i结尾最后一步是下降的最长湍流子数组长度2. 状态转移arr[i] arr[i-1]f[i] g[i-1]1arr[i] arr[i-1]g[i] f[i-1]1arr[i]arr[i-1]不构成湍流f,g都不变3. 初始化f、g数组全部初始化为1单个元素自身长度为14. 填表顺序从左往右两表一起填5. 返回值两个dp表里面的最大值C代码class Solution { public: int maxTurbulenceSize(vectorint arr) { int n arr.size(); vectorint f(n, 1), g(n, 1); int ret 1; for(int i 1; i n; i) { if(arr[i - 1] arr[i]) f[i] g[i - 1] 1; else if(arr[i - 1] arr[i]) g[i] f[i - 1] 1; ret max(ret, max(f[i], g[i])); } return ret; } };25. 单词拆分LeetCode 139 medium题目描述算法思路1. 状态表示对于线性 dp我们可以用「经验 题目要求」来定义状态表示i. 以某个位置为结尾巴拉巴拉ii. 以某个位置为起点巴拉巴拉。这里我们选择比较常用的方式以某个位置为结尾结合题目要求定义一个状态表示dp[i] 表示[0i] 区间内的字符串能否被字典中的单词拼接而成。2. 状态转移方程对于 dp[i]为了确定当前的字符串能否由字典里面的单词构成根据最后一个单词的起始位置 j我们可以将其分解为前后两部分i. 前面一部分 [0j - 1] 区间的字符串ii. 后面一部分 [ji] 区间的字符串。其中前面部分我们可以在 dp[j - 1] 中找到答案后面部分的子串可以在字典里面找到。因此我们得出一个结论当我们在从 0 ~ i 枚举 j 的时候只要 dp[j - 1] true 并且后面部分的子串 s.substr(j, i - j 1) 能够在字典中找到那么 dp[i] true。3. 初始化可以在最前面加上一个「辅助结点」帮助我们初始化。使用这种技巧要注意两个点i. 辅助结点里面的值要「保证后续填表是正确的」ii.「下标的映射关系」。在本题中最前面加上一个格子并且让 dp[0] true可以理解为空串能够拼接而成。其中为了方便处理下标的映射关系我们可以将字符串前面加上一个占位符 s s这样就没有下标的映射关系的问题了同时还能处理「空串」的情况。4. 填表顺序填表顺序从左往右。5. 返回值由「状态表示」可得返回 dp[n] 位置的布尔值。6. 哈希表优化的小细节在状态转移中我们需要判断后面部分的子串「是否在字典」之中因此会「频繁的用到查询操作」。为了节省效率我们可以提前把「字典中的单词」存入到「哈希表」中。C 算法代码class Solution { public: bool wordBreak(string s, vectorstring wordDict) { // 优化一将字典里面的单词存在哈希表里面 unordered_setstring hash; for(auto s : wordDict) hash.insert(s); int n s.size(); vectorbool dp(n 1); dp[0] true; // 保证后续填表是正确的 s s; // 使原始字符串的下标统一1 for(int i 1; i n; i) // 填 dp[i] { for(int j i; j 1; j--) // 最后一个单词的起始位置 { if(dp[j - 1] hash.count(s.substr(j, i - j 1))) { dp[i] true; break; // 优化二 } } } return dp[n]; } };✅ 知识点整理1. DP状态定义dp[i]字符串前i个字符是否可以被字典单词拼接成功。dp[0]true代表空串合法是经典辅助初始位技巧。2. 状态转移遍历分割点j如果dp[j-1]为true并且子串s[j~i]存在于字典 → dp[i]true含义前面j-1长度可以拼出来j~i这一段是字典单词那么前i个字符就可以拼出。3. 哈希优化unordered_set存储字典单词子串查找从O(k)变为O(1)加快查询速度。4. 下标处理技巧s s 把原字符串下标整体后移一位dp数组下标和字符串长度对齐规避边界判断的麻烦。5. 填表顺序从左向右因为求dp[i]依赖前面dp[0]~dp[i-1]的结果。6. 时间复杂度O(n^2)n是字符串长度两层循环substr截取子串。空间复杂度O(n)dp数组哈希集合。7. 优化点找到一种合法分割就直接break不用继续枚举j。26. 环绕字符串中唯一的子字符串LeetCode 467 medium题目描述算法思路1. 状态表示dp[i]以i位置字符结尾在base中出现的连续子串长度。2. 状态转移长度1一定合法长度1判断是否连续 s[i-1]1 s[i] 或者 s[i-1]z s[i]a满足dp[i] dp[i-1]1否则dp[i]1重点去重 相同字符结尾只保留最大长度放到hash[26]数组最后累加总和3. 初始化dp全部初始化为14. 填表顺序从左往右5. 返回值hash数组所有元素累加和C代码class Solution { public: int findSubstringInWraproundString(string s) { int n s.size(); vectorint dp(n, 1); for(int i 1; i n; i) { if(s[i - 1] s[i] - 1 || (s[i - 1] z s[i] a)) dp[i] dp[i - 1] 1; } int hash[26] {0}; for(int i 0; i n; i) { hash[s[i] - a] max(hash[s[i] - a], dp[i]); } int sum 0; for(auto x : hash) sum x; return sum; } }; 统一知识点总结一、通用解题模板线性DP以结尾型适用于子数组、子串、连续区间类题目1. 状态定义套路dp[i] 表示以第i个元素结尾的满足条件的量。✅ 好处子数组具有连续性新增元素只需要和前一个状态推导。2. 分类讨论子数组只有当前一个元素子数组长度1接上前面以i-1结尾的子数组3. 初始化技巧增加辅助结点 dp[0]偏移下标避免i1的时候越界辅助结点的值要保证转移方程计算正确。4. 填表顺序固定从左往右dp[i]依赖dp[i-1]5. 返回值分三类求全局最优返回dp数组最大值最大子数组和、乘积最大、最长湍流求全部方案数量返回dp数组累加和等差数列划分求n位置状态返回dp[n]单词拆分二、什么时候需要双dp数组f,g当单一状态无法记录足够信息时需要两个dp数组保存两种状态1. 乘积最大子数组要同时保存最大乘积、最小乘积负数相乘反转大小2. 乘积为正数最长子数组保存正乘积长度、负乘积长度3. 最长湍流子数组保存上升结尾长度、下降结尾长度核心思想一个状态的结果会因为正负/方向翻转所以同时维护两种极值/状态。易错点汇总1. 子数组必须连续和子序列区分开2. 乘积类题目负数会翻转最值只用一个dp数组一定错3. 环形子数组存在边界特例数组全负数不能用sum-gmin4. 计数类题目等差数列划分dp存以i结尾的数量答案是总和不是最大值5. 环绕字符串题目存在大量重复子串必须去重不能直接累加dp数组