当前位置：首页 > backend >正文

【动态规划】简单多状态（一）

backend 2025/8/11 18:59:33

📝前言说明：

本专栏主要记录本人的动态规划的学习以及LeetCode刷题记录，按专题划分
每题主要记录：（1）本人解法 + 本人屎山代码；（2）优质解法 + 优质代码；（3）精益求精，更好的解法和独特的思想（如果有的话）
文章中的理解仅为个人理解。如有错误，感谢纠错

🎬个人简介：努力学习ing
📋本专栏：C++刷题专栏
📋其他专栏：C语言入门基础，python入门基础，C++学习笔记，Linux
🎀CSDN主页愚润泽

你可以点击下方链接，进行不同专题的动态规划的学习

点击链接	开始学习
斐波那契数列模型	路径问题
简单多状态（一）	简单多状态（二）
子数组系列（一）	子数组系列（二）
子序列问题（一）	子序列问题（二）
回文串问题	两个数组的dp问题（一）
两个数组的dp问题（二）	01背包问题
完全背包	二维的背包问题
其他

题目

面试题 17.16. 按摩师
- 优质解
213. 打家劫舍 II
- 优质解
740. 删除并获得点数
- 优质解
LCR 091. 粉刷房子
- 个人解

面试题 17.16. 按摩师

题目链接：https://leetcode.cn/problems/the-masseuse-lcci/description/

在这里插入图片描述

优质解

思路：

状态表示：dp[i] ：选择到 i 位置时，此时的最⻓预约时⻓。
- 但是，在我们进行状态表示的时候，根据题意：可以发现 dp[i] 出现了两种状态：当前位置被选和当前位置不被选。【这就是多状态，我们需要使用两个dp表】
- f[i] 表⽰：选择到 i 位置时， nums[i] 必选，此时的最⻓预约时⻓
- g[i] 表⽰：选择到 i 位置时，nums[i] 不选，此时的最⻓预约时⻓。
状态转移方程
- 对于 f[i] ：
  - 如果 nums[i] 必选，则i - 1 位置一定是不选的，因此 f[i] = g[i - 1] + nums[i]。
- 对于 g[i] ：
  - 如果 nums[i] 不选，那么 i - 1 位置可选 / 可不选。因此，我们需要知道 i - 1 位置上选或者不选两种情况下的最⻓时⻓，因此 g[i] = max(f[i - 1], g[i - 1])
初始化：注意填写 0位置时，可能会越界，所以我们先填写f[0] == nums[0]，g[0] == 0
填表顺序：两个数组一起填，从左往右
返回值：max(f[n - 1], g[n - 1])

代码：

class Solution {
public:int massage(vector<int>& nums) {int n = nums.size();if(n == 0) return 0;vector<int> f(n, 0);auto g = f;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]);}
};

时间复杂度：O(n)
空间复杂度：O(n)

213. 打家劫舍 II

题目链接：https://leetcode.cn/problems/house-robber-ii/description/
在这里插入图片描述
注意：数组中的首尾数字虽然相同，但是是不同的房间。

优质解

思路：

把环形问题，拆成两个单排
- 偷第⼀个房屋时，不能偷最后⼀个房⼦，因此就是偷 [0, n - 2] 区间的房⼦
- 不偷第⼀个房屋时，可以偷最后⼀个房⼦，因此就是偷 [1, n - 1] 区间的房⼦

代码：

class Solution {
public:int rob1(vector<int>& nums, int left, int right){if(left > right) return 0;int n = nums.size();vector<int> f(n, 0);auto g = f;f[left] = nums[left];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]);}int rob(vector<int>& nums) {int n = nums.size();// 选 0，不选 1，不选 n - 1（下标）int x = nums[0] + rob1(nums, 2, n - 2);// 不选 0int y = rob1(nums, 1, n - 1);return max(x, y);}
};

时间复杂度：O(n)
空间复杂度：O(n)

740. 删除并获得点数

题目链接：https://leetcode.cn/problems/delete-and-earn/description/
在这里插入图片描述

优质解

思路：

打家劫舍的变形：选了nums[i]就不能选nums[i] - 1和nums[i] + 1（即：不能选数值相邻的两个）
问题在于：打家劫舍的数组没有重复元素，而本题有
我们只需：把相同的数字x累加到数组的x下标位置，其他位置设置成 0（然后做一次打家劫舍）

代码：

class Solution {
public:int deleteAndEarn(vector<int>& nums) {vector<int> numss(10001, 0);for(auto x:nums) numss[x] += x;int n = numss.size();vector<int> f(n, 0);auto g = f;f[0] = numss[0];for(int i = 1; i < n; i++){f[i] = g[i - 1] + numss[i];g[i] = max(g[i - 1], f[i - 1]);}return max(f[n - 1], g[n - 1]);}
};

时间复杂度：O(n)
空间复杂度：O(n)

LCR 091. 粉刷房子

题目链接：https://leetcode.cn/problems/JEj789/description/
在这里插入图片描述

个人解

思路：

三个dp(f, g, h)【当然用一个二维数组也行】, 表示当前房子粉刷成红 / 蓝 / 绿时的最小花费成本
状态转移方程：f[i] = costs[i][0] + min(g[i - 1], h[i - 1]);
- 代表第 i 个房子刷红色，前面取刷蓝 / 绿的最小值（其他同理）
填表顺序：三个表并行填
返回值：min(f[n - 1], g[n - 1], h[n - 1]);

用时：
屎山代码：

class Solution {
public:int minCost(vector<vector<int>>& costs) {int n = costs.size();vector<int> f(n, 0);auto g = f, h = f;f[0] = costs[0][0]; g[0] = costs[0][1]; h[0] = costs[0][2];for(int i = 1; i < n; i++){f[i] = costs[i][0] + min(g[i - 1], h[i - 1]);g[i] = costs[i][1] + min(f[i - 1], h[i - 1]);h[i] = costs[i][2] + min(f[i - 1], g[i - 1]);}return min(min(f[n - 1], g[n - 1]), h[n - 1]);}
};