简单多状态 dp 问题当一个问题可以分解为多个相互关联的子问题并且每个子问题本身有几种不同的“状态”或“处境”这些状态之间的转换规则明确时就适用于“简单多状态动态规划”。详细解释为了更清楚地理解我们把这句话拆解一下1. 题目类型与特征这类问题的典型特征是对于每个步骤或每个决策点对象并非只有单一情况而是可能处于多个通常是2-4个不同的“状态”之一。你需要同时考虑所有这些状态并理清它们之间是如何转换的。常见的状态类型包括持有/空手状态比如股票买卖问题中你可能是“持有股票”或“未持有股票”。选择/未选择状态比如打家劫舍问题中对于当前这家可能是“偷了”或“没偷”。不同限制下的状态比如带有冷冻期或手续费的问题状态会更多如“冷冻期”状态。颜色交替状态比如粉刷房子问题房子可能被刷成“红色”、“蓝色”或“绿色”。2. 什么题目适用一个题目适合用简单多状态DP来解决通常满足以下三个条件最优子结构大问题的最优解可以由小问题的最优解推导出来。这是所有DP问题的基础。重叠子问题在递归求解过程中会反复遇到相同的子问题。有限状态集合这是“多状态”DP的关键。问题的每个阶段都可以被清晰地划分为几个有限的状态并且这些状态是解决问题的核心。经典例题打家劫舍问题状态对于每一间房子有两种状态dp[i][0]表示不偷第 i 间房能获得的最大金额dp[i][1]表示偷第 i 间房能获得的最大金额。状态转移不偷第 i 间房 (dp[i][0])那么第 i-1 间房可以偷也可以不偷取最大值。dp[i][0] max(dp[i-1][0], dp[i-1][1])偷第 i 间房 (dp[i][1])那么第 i-1 间房一定不能偷。dp[i][1] dp[i-1][0] nums[i]买卖股票的最佳时机含冷冻期状态通常定义三种状态dp[i][0]: 第 i 天结束时持有股票的最大利润。dp[i][1]: 第 i 天结束时不持有股票且处于冷冻期即当天卖出了股票的最大利润。dp[i][2]: 第 i 天结束时不持有股票且不处于冷冻期的最大利润。状态转移这三个状态之间有着明确的转换关系例如从“持有”可以转到“冷冻期”从“不持有非冷冻”可以转到“持有”。粉刷房子问题状态dp[i][0],dp[i][1],dp[i][2]分别表示将第 i 栋房子刷成红色、蓝色、绿色的最小成本。状态转移为了避免相邻房子同色刷当前颜色的成本加上前一个房子刷成其他颜色的最小成本。例如dp[i][0] cost[i][0] min(dp[i-1][1], dp[i-1][2])。总结简单多状态DP就是识别出问题中那些有限的、关键的状态然后像管理多个并行的“账户”一样为每个状态单独维护一个DP数组或变量并根据明确的规则状态转移方程来更新这些“账户”的余额最终答案往往就是所有状态在最后一步中的最大值或最小值。题目练习面试题 17.16. 按摩师 - 力扣LeetCode算法动态规划算法思路1. 状态表示对于简单的线性 dp我们可以用「经验题目要求」来定义状态表示以某个位置为结尾巴拉巴拉以某个位置为起点巴拉巴拉。这里我们选择比较常用的方式以某个位置为结尾结合题目要求定义一个状态表示dp[i] 表示选择到 i 位置时此时的最长预约时长。但是我们这个题在 i 位置的时候会面临「选择」或者「不选择」两种抉择所依赖的状态需要细分f[i] 表示选择到 i 位置时nums[i] 必选此时的最长预约时长g[i] 表示选择到 i 位置时nums[i] 不选此时的最长预约时长。2. 状态转移方程因为状态表示定义了两个因此我们的状态转移方程也要分析两个对于 f[i]如果 nums[i] 必选那么我们仅需知道 i−1 位置在不选的情况下的最长预约时长然后加上 nums[i] 即可因此。对于 g[i]如果 nums[i] 不选那么 i−1 位置上选或者不选都可以。因此我们需要知道 i−1 位置上选或者不选两种情况下的最长时长因此3. 初始化这道题的初始化比较简单因此无需加辅助节点仅需初始化 f[0]nums[0],g[0]0 即可。4. 填表顺序根据「状态转移方程」得「从左往右两个表一起填」。5. 返回值根据「状态表示」应该返回。class Solution { public: int massage(vectorint nums) { int n nums.size(); if(!n) return 0; vectorint f(n); vectorint g(n); f[0] nums[0]; for(int i 1; i n; i) { f[i] g[i - 1] nums[i]; g[i] max(g[i - 1], f[i - 1]); } return max(f[n - 1], g[n - 1]); } };213. 打家劫舍 II - 力扣LeetCode解法动态规划算法思路这一个问题是 「打家劫舍」 问题的变形。上一个问题是一个 「单排」的模式这一个问题是一个「环形」的模式也就是首尾是相连的。但是我们可以将「环形」问题转化为「两个单排」** 问题a. 偷第一个房屋时的最大金额x此时不能偷最后一个房子因此就是偷[0, n - 2]区间的房子b. 不偷第一个房屋时的最大金额y此时可以偷最后一个房子因此就是偷[1, n - 1]区间的房子两种情况下的 「最大值」就是最终的结果。因此问题就转化成求 「两次单排结果的最大值」。class Solution { public: int _rob(vectorint nums, int l, int r) { if(l r) return 0; int n nums.size(); vectorint f(n); vectorint g(n); f[l] nums[l]; for(int i l 1; i r; i) { f[i] g[i - 1] nums[i]; g[i] max(f[i - 1], g[i - 1]); } return max(f[r], g[r]); } int rob(vectorint nums) { int n nums.size(); return max(nums[0] _rob(nums, 2, n - 2), _rob(nums, 1, n - 1)); } };740. 删除并获得点数 - 力扣LeetCode解法动态规划算法思路其实这道题依旧是 「打家劫舍」 问题的变型。我们注意到题目描述选择x数字的时候x - 1与x 1是不能被选择的。像不像 「打家劫舍」 问题中选择i位置的金额之后就不能选择i - 1位置以及i 1位置的金额呢因此我们可以创建一个大小为10001根据题目的数据范围的hash数组将nums数组中每一个元素x累加到hash数组下标为x的位置处然后在hash数组上来一次 「打家劫舍」 即可。class Solution { public: int deleteAndEarn(vectorint nums) { int sum[10001]{0}; for (auto e : nums) {sum[e] e;} vectorintf(10001); vectorintg(10001); for (int i 1; i 10001; i) { f[i] g[i - 1]sum[i]; g[i] max(f[i - 1], g[i - 1]); } return max(f[10000], g[10000]); } };LCR 091. 粉刷房子 - 力扣LeetCode解法动态规划算法思路1. 状态表示对于线性dp我们可以用 「经验 题目要求」 来定义状态表示ⅰ. 以某个位置为结尾巴拉巴拉ⅱ. 以某个位置为起点巴拉巴拉。这里我们选择比较常用的方式以某个位置为结尾结合题目要求定义一个状态表示但是我们这个题在i位置的时候会面临 「红」「蓝」「绿」 三种抉择所依赖的状态需要细分dp[i][0]表示粉刷到i位置的时候最后一个位置粉刷上 「红色」此时的最小花费dp[i][1]表示粉刷到i位置的时候最后一个位置粉刷上 「蓝色」此时的最小花费dp[i][2]表示粉刷到i位置的时候最后一个位置粉刷上 「绿色」此时的最小花费。2. 状态转移方程因为状态表示定义了三个因此我们的状态转移方程也要分析三个对于dp[i][0]如果第i个位置粉刷上 「红色」那么i - 1位置上可以是「蓝色」或者「绿色」。因此我们需要知道粉刷到i - 1位置上的时候粉刷上「蓝色」或者「绿色」 的最小花费然后加上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][0], dp[i - 1][1]) costs[i - 1][2]。3. 初始化可以在最前面加上一个 「辅助结点」帮助我们初始化。使用这种技巧要注意两个点ⅰ. 辅助结点里面的值要 「保证后续填表是正确的」ⅱ.「下标的映射关系」。在本题中添加一个节点并且初始化为0即可。4. 填表顺序根据 「状态转移方程」得「从左往右三个表一起填」。5. 返回值根据 「状态表示」应该返回最后一个位置粉刷上三种颜色情况下的最小值因此需要返回min(dp[n][0], min(dp[n][1], dp[n][2]))。class Solution { public: int minCost(vectorvectorint costs) { 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][0], dp[i - 1][1]) costs[i - 1][2]; } return min(dp[n][0], min(dp[n][1], dp[n][2])); } };309. 买卖股票的最佳时机含冷冻期 - 力扣LeetCode解法动态规划算法思路1. 状态表示对于线性dp我们可以用 「经验 题目要求」 来定义状态表示ⅰ. 以某个位置为结尾巴拉巴拉ⅱ. 以某个位置为起点巴拉巴拉。这里我们选择比较常用的方式以某个位置为结尾结合题目要求定义一个状态表示由于有 「买入」「可交易」「冷冻期」 三个状态因此我们可以选择用三个数组其中dp[i][0]表示第i天结束后处于 「买入」 状态此时的最大利润dp[i][1]表示第i天结束后处于 「可交易」 状态此时的最大利润dp[i][2]表示第i天结束后处于 「冷冻期」 状态此时的最大利润。2. 状态转移方程我们要谨记规则ⅰ. 处于 「买入」 状态的时候我们现在有股票此时不能买股票只能继续持有股票或者卖出股票ⅱ. 处于 「卖出」 状态的时候如果 「在冷冻期」不能买入如果 「不在冷冻期」才能买入。对于dp[i][0]我们有 「两种情况」 能到达这个状态ⅰ. 在i - 1天持有股票此时最大收益应该和i - 1天的保持一致dp[i - 1][0]ⅱ. 在i天买入股票那我们应该选择i - 1天不在冷冻期的时候买入由于买入需要花钱所以此时最大收益为dp[i - 1][1] - prices[i]。两种情况应取最大值因此dp[i][0] max(dp[i - 1][0], dp[i - 1][1] - prices[i])。对于dp[i][1]我们有 「两种情况」 能到达这个状态ⅰ. 在i - 1天的时候已经处于冷冻期然后啥也不干到第i天此时对应的状态为dp[i - 1][2]ⅱ. 在i - 1天的时候手上没有股票也不在冷冻期但是依旧啥也不干到第i天此时对应的状态为dp[i - 1][1]两种情况应取最大值因此dp[i][1] max(dp[i - 1][1], dp[i - 1][2])。对于dp[i][2]我们只有 「一种情况」 能到达这个状态ⅰ. 在i - 1天的时候卖出股票。因此对应的状态转移为dp[i][2] dp[i - 1][0] prices[i]。3. 初始化三种状态都会用到前一个位置的值因此需要初始化每一行的第一个位置dp[0][0]此时要想处于 「买入」 状态必须把第一天的股票买了因此dp[0][0] -prices[0]dp[0][1]啥也不用干即可因此dp[0][1] 0dp[0][2]手上没有股票买一下卖一下就处于冷冻期此时收益为0因此dp[0][2] 0。4. 填表顺序根据 「状态表示」我们要三个表一起填每一个表「从左往右」。5. 返回值应该返回 「卖出状态」 下的最大值因此应该返回max(dp[n - 1][1], dp[n - 1][2])。class Solution { public: int maxProfit(vectorint prices) { int n prices.size(); vectorvectorint dp(n, vectorint(3)); dp[0][0] -prices[0]; for (int i 1; i n; i) { dp[i][0] max(dp[i - 1][1] - prices[i], dp[i - 1][0]); 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]); } };714. 买卖股票的最佳时机含手续费 - 力扣LeetCode解法动态规划算法思路1. 状态表示对于线性dp我们可以用 「经验 题目要求」 来定义状态表示ⅰ. 以某个位置为结尾巴拉巴拉ⅱ. 以某个位置为起点巴拉巴拉。这里我们选择比较常用的方式以某个位置为结尾结合题目要求定义一个状态表示由于有 「买入」「可交易」 两个状态因此我们可以选择用两个数组其中f[i]表示第i天结束后处于 「买入」 状态此时的最大利润g[i]表示第i天结束后处于 「卖出」 状态此时的最大利润。2. 状态转移方程我们选择在 「卖出」的时候支付这个手续费那么在「买入」 的时候就不用再考虑手续费的问题。对于f[i]我们有两种情况能到达这个状态ⅰ. 在i - 1天 「持有」 股票第i天啥也不干。此时最大收益为f[i - 1]ⅱ. 在i - 1天的时候 「没有」 股票在第i天买入股票。此时最大收益为g[i - 1] - prices[i]两种情况下应该取最大值因此f[i] max(f[i - 1], g[i - 1] - prices[i])。对于g[i]我们也有两种情况能够到达这个状态ⅰ. 在i - 1天 「持有」 股票但是在第i天将股票卖出。此时最大收益为f[i - 1] prices[i] - fee记得手续费ⅱ. 在i - 1天 「没有」 股票然后第i天啥也不干。此时最大收益为g[i - 1]两种情况下应该取最大值因此g[i] max(g[i - 1], f[i - 1] prices[i] - fee)。3. 初始化由于需要用到前面的状态因此需要初始化第一个位置。对于f[0]此时处于 「买入」 状态因此f[0] -prices[0]对于g[0]此时处于 「没有股票」 状态啥也不干即可获得最大收益因此g[0] 0。4. 填表顺序毫无疑问是 「从左往右」但是两个表需要一起填。5. 返回值应该返回 「卖出」 状态下最后一天的最大值收益g[n - 1]。class Solution { public: int maxProfit(vectorint prices, int fee) { int n prices.size(); vectorint f(n); auto g f; f[0] -prices[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]; } };123. 买卖股票的最佳时机 III - 力扣LeetCode解法动态规划算法思路1. 状态表示对于线性dp我们可以用 「经验 题目要求」 来定义状态表示ⅰ. 以某个位置为结尾巴拉巴拉ⅱ. 以某个位置为起点巴拉巴拉。这里我们选择比较常用的方式以某个位置为结尾结合题目要求定义一个状态表示由于有 「买入」「可交易」 两个状态且这道题里面还有交易次数的限制因此我们还需要再加上一维用来表示交易次数。其中f[i][j]表示第i天结束后完成了j次交易处于 「买入」 状态此时的最大利润g[i][j]表示第i天结束后完成了j次交易处于 「卖出」 状态此时的最大利润。2. 状态转移方程对于f[i][j]我们有两种情况到这个状态ⅰ. 在i - 1天的时候交易了j次处于 「买入」 状态第i天啥也不干即可。此时最大利润为f[i - 1][j]ⅱ. 在i - 1天的时候交易了j次处于 「卖出」 状态第i天的时候把股票买了。此时的最大利润为g[i - 1][j] - prices[i]。综上我们要的是 「最大利润」因此是两者的最大值f[i][j] max(f[i - 1][j], g[i - 1][j] - prices[i])。对于g[i][j]我们也有两种情况可以到达这个状态ⅰ. 在i - 1天的时候交易了j次处于 「卖出」 状态第i天啥也不干即可。此时的最大利润为g[i - 1][j]ⅱ. 在i - 1天的时候交易了j - 1次处于 「买入」 状态第i天把股票卖了然后就完成了j笔交易。此时的最大利润为f[i - 1][j - 1] 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])3. 初始化由于需要用到i 0时的状态因此我们初始化第一行即可。当处于第0天的时候只能处于 「买入过一次」 的状态此时的收益为-prices[0]因此f[0][0] -prices[0]。为了取max的时候一些不存在的状态 「起不到干扰」的作用我们统统将它们初始化为-INF用INT_MIN在计算过程中会有「溢出」 的风险这里INF折半取0x3f3f3f3f足够小即可。4. 填表顺序从 「上往下填」每一行每一行「从左往右」两个表「一起填」。5. 返回值返回处于 「卖出状态」的最大值但是我们也「不知道是交易了几次」因此返回g表最后一行的最大值。class Solution { public: const int INF 0X3f3f3f3f; int maxProfit(vectorint prices) { 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 2; 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; } };188. 买卖股票的最佳时机 IV - 力扣LeetCode解法动态规划算法思路1. 状态表示为了更加清晰的区分 「买入」和「卖出」我们换成「有股票」和「无股票」 两个状态。f[i][j]表示第i天结束后完成了j笔交易此时处于 「有股票」 状态的最大收益g[i][j]表示第i天结束后完成了j笔交易此时处于 「无股票」 状态的最大收益。2. 状态转移方程对于f[i][j]我们也有两种情况能在第i天结束之后完成j笔交易此时手里 「有股票」 的状态ⅰ. 在i - 1天的时候手里 「有股票」并且交易了j次。在第i天的时候啥也不干。此时的收益为f[i - 1][j]ⅱ. 在i - 1天的时候手里 「没有股票」并且交易了j次。在第i天的时候买了股票。那么i天结束之后我们就有股票了。此时的收益为g[i - 1][j] - prices[i]上述两种情况我们需要的是 「最大值」因此f的状态转移方程为f[i][j] max(f[i - 1][j], g[i - 1][j] - prices[i])对于g[i][j]我们有下面两种情况能在第i天结束之后完成j笔交易此时手里 **「没有股票」** 的状态ⅰ. 在i - 1天的时候手里 「没有股票」并且交易了j次。在第i天的时候啥也不干。此时的收益为g[i - 1][j]ⅱ. 在i - 1天的时候手里 「有股票」并且交易了j - 1次。在第i天的时候把股票卖了。那么i天结束之后我们就交易了j次。此时的收益为f[i - 1][j - 1] prices[i]上述两种情况我们需要的是 「最大值」因此g的状态转移方程为g[i][j] max(g[i - 1][j], f[i - 1][j - 1] prices[i])3. 初始化由于需要用到i 0时的状态因此我们初始化第一行即可。当处于第0天的时候只能处于 「买入过一次」 的状态此时的收益为-prices[0]因此f[0][0] -prices[0]。为了取max的时候一些不存在的状态 「起不到干扰」的作用我们统统将它们初始化为-INF用INT_MIN在计算过程中会有「溢出」 的风险这里INF折半取0x3f3f3f3f足够小即可。4. 填表顺序从上往下填每一行每一行从左往右两个表一起填。5. 返回值返回处于卖出状态的最大值但是我们也不知道是交易了几次因此返回g表最后一行的最大值。优化点我们的交易次数是不会超过整个天数的一半的因此我们可以先把k处理一下优化一下问题的规模k min(k, n / 2)class Solution { public: const int INF 0X3f3f3f3f; int maxProfit(int k, vectorint prices) { 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 ret 0; for(int j 0; j k; j) {ret max(ret, g[n - 1][j]);} return ret; } };