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

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

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

  01.按摩师

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

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

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

  示例 1：

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

  输出： 4

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

  示例 2：

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

  输出： 12

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

  示例 3：

  输入： [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])); } };