算法沉淀——动态规划之简单多状态 dp 问题（上）（leetcode真题剖析）

02-27 阅读 0评论

$算法沉淀——动态规划之简单多状态 dp 问题（上）（leetcode真题剖析）,算法沉淀——动态规划之简单多状态 dp 问题（上）（leetcode真题剖析）,词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,使用,我们,方法,第2张$

（图片来源网络，侵删）

算法沉淀——动态规划之简单多状态 dp 问题上

01.按摩师
02.打家劫舍 II
03.删除并获得点数
04.粉刷房子
01.按摩师

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

一个有名的按摩师会收到源源不断的预约请求，每个预约都可以选择接或不接。在每次预约服务之间要有休息时间，因此她不能接受相邻的预约。给定一个预约请求序列，替按摩师找到最优的预约集合（总预约时间最长），返回总的分钟数。

注意：本题相对原题稍作改动

示例 1：

输入： [1,2,3,1]

输出： 4
$算法沉淀——动态规划之简单多状态 dp 问题（上）（leetcode真题剖析）,算法沉淀——动态规划之简单多状态 dp 问题（上）（leetcode真题剖析）,词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,使用,我们,方法,第3张$
（图片来源网络，侵删）

解释：选择 1 号预约和 3 号预约，总时长 = 1 + 3 = 4。

示例 2：

输入： [2,7,9,3,1]

输出： 12

解释：选择 1 号预约、 3 号预约和 5 号预约，总时长 = 2 + 9 + 1 = 12。

示例 3：
$算法沉淀——动态规划之简单多状态 dp 问题（上）（leetcode真题剖析）,算法沉淀——动态规划之简单多状态 dp 问题（上）（leetcode真题剖析）,词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,使用,我们,方法,第4张$
（图片来源网络，侵删）

输入： [2,1,4,5,3,1,1,3]

输出： 12

解释：选择 1 号预约、 3 号预约、 5 号预约和 8 号预约，总时长 = 2 + 4 + 3 + 3 = 12。

思路
1. 状态表达：我们定义两个状态数组，f 和 g：
  - f[i] 表示：选择到位置 i 时，此时的最长预约时长，且 nums[i] 必须选。
  - g[i] 表示：选择到位置 i 时，此时的最长预约时长，nums[i] 不选。
  - 状态转移方程：对于 f[i]：
    - 如果 nums[i] 必须选，那么我们仅需知道 i - 1 位置在不选的情况下的最长预约时长，然后加上 nums[i] 即可，因此 f[i] = g[i - 1] + nums[i]。
      对于 g[i]：
      - 如果 nums[i] 不选，那么 i - 1 位置上选或者不选都可以。因此，我们需要知道 i - 1 位置上选或者不选两种情况下的最长时长，因此 g[i] = max(f[i - 1], g[i - 1])。
      - 初始化：由于这道题的初始化比较简单，无需加辅助节点，仅需初始化 f[0] = nums[0], g[0] = 0 即可。
      - 填表顺序：根据状态转移方程，从左往右，两个表一起填。
      - 返回值：根据状态表达，我们应该返回 max(f[n - 1], g[n - 1])。
代码
```
class Solution {
public:
    int massage(vector& nums) {
        int n = nums.size();
        if(n==0) return 0;
        vector f(n);
        vector g(n);
        f[0] = nums[0];
        for (int i = 1; i  
02.打家劫舍 II 
题目链接：https://leetcode.cn/problems/house-robber-ii/ 
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。 
给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。 
示例 1： 
输入：nums = [2,3,2]
输出：3
解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
 
示例 2： 
输入：nums = [1,2,3,1]
输出：4
解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
     偷窃到的最高金额 = 1 + 3 = 4 。
 
示例 3： 
输入：nums = [1,2,3]
输出：3
 
提示： 
```
- 1 public: int rob(vector int n=nums.size(); return max(nums[0]+rob1(nums,2,n-2),rob1(nums,1,n-1)); } int rob1(vector if(startend) return 0; int n=nums.size(); vector f[i]=g[i-1]+nums[i]; g[i]=max(g[i-1],f[i-1]); } return max(g[end],f[end]); } }; public: int deleteAndEarn(vector int hash[10001] = {0}; for(int& x:nums) hash[x]+=x; vector f[i]=g[i-1]+hash[i]; g[i]=max(g[i-1],f[i-1]); } return max(f[10000],g[10000]); } }; public: int minCost(vector int n=costs.size(); vector 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])); } };