[Algorithm][动态规划][简单多状态DP问题][按摩师][打家劫舍Ⅱ][删除并获得点数][粉刷房子]详细讲解

1.按摩师

1.题目链接

• 按摩师

2.算法思路详解

• 思路：

  • 确定状态表示 -> dp[i]的含义

    • 选择到i位置的时候，此时的最长预约时长
    • 本题，状态表示还可以继续细分：
      • f[i]：选择到i位置的时候，nums[i]必选，此时的最长预约时长
      • g[i]：选择到i位置的时候，nums[i]不选，此时的最长预约时长

  • 推导状态转移方程

    • f[i] = g[i - 1] + nums[i]
    • g[i] = max(f[i - 1], g[i - 1])
      

  • 初始化：f[0] = nums[0], g[0] = 0

  • 确定填表顺序：从左往右，两个表一起填

  • 确定返回值：max(f[n - 1], g[n - 1])

3.代码实现

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

2.打家劫舍 II

1.题目链接

• 打家劫舍 II

2.算法思路详解

• 思路解析：本题比打家劫舍Ⅰ只多了环形问题，那么只需将环形问题分类讨论(依据nums[0])，拆解为两个线性的打家劫舍Ⅰ问题即可
  • 第一个位置偷：nums[0] + _rob[2, n - 2] <— 第二个位置和最后一个位置不偷
  • 第一个位置不偷：_rob(1, n - 1) <— 偷第二个位置和最后一个位置
• 思路：

  • 确定状态表示 -> dp[i]的含义

    • 到i位置的时候，此时的最大金额
    • 本题，状态表示还可以继续细分：
      • f[i]：偷到i位置的时候，nums[i]必偷，此时的最大金额
      • g[i]：偷到i位置的时候，nums[i]不偷，此时的最大金额

  • 推导状态转移方程

    • f[i] = g[i - 1] + nums[i]
    • g[i] = max(f[i - 1], g[i - 1])
      

  • 初始化：f[0] = nums[0], g[0] = 0

  • 确定填表顺序：从左往右，两个表一起填

  • 确定返回值：max(f[n - 1], g[n - 1])

3.代码实现

class Solution
{
public:int rob(vector<int>& nums) {int n = nums.size();// 分类讨论，取两种情况中的最大值return max(nums[0] + _rob(nums, 2, n - 2), _rob(nums, 1, n - 1));}int _rob(vector<int>& nums, int left, int right){if(left > right) return 0;int n = nums.size();vector<int> f(n); // 选vector<int> g(n); // 不选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]);}
};

3.删除并获得点数

1.题目链接

• 删除并获得点数

2.算法思路详解

• 思路解析：本题可以先做一个预处理，将问题转化为打家劫舍

  • 思路：
    • 打家劫舍要求访问数组中的数的顺序是连续的，但本题原始数组显然不符合要求
    • 虽然原始数组数值不符合要求，但是经过转换，数组下标是可以符合顺序连续的
  • 做法：
    • 将原始数组中的数，统计到arr中，然后在arr中，做一次打家劫舍问题即可
    • 此时，数值相同的值的和可以被其本身值作为arr的下标索引到 <— hash[x] = sum(x)
    • arr[i]：i这个数出现的总和
      

• 思路：

  • 确定状态表示 -> dp[i]的含义

    • 到i位置的时候，此时获得的最大点数
    • 本题，状态表示还可以继续细分：
      • f[i]：选到i位置的时候，nums[i]必选，此时获得的最大点数
      • g[i]：选到i位置的时候，nums[i]不选，此时获得的最大点数

  • 推导状态转移方程

    • f[i] = g[i - 1] + arr[i]
    • g[i] = max(f[i - 1], g[i - 1])
      

  • 初始化：f[0] = arr[0], g[0] = 0

  • 确定填表顺序：从左往右，两个表一起填

  • 确定返回值：max(f[n], g[n])

3.代码实现

int deleteAndEarn(vector<int>& nums) 
{sort(nums.begin(), nums.end());int n = nums.back(); // maxvector<int> arr(n + 1);for(auto& x : nums){arr[x] += x;}vector<int> f(n + 1);vector<int> g(n + 1);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], g[n]);
}

4.粉刷房子

1.题目链接

• 粉刷房子

2.算法思路详解

• 思路：

  • 确定状态表示 -> dp[i][j]的含义：i -> 到了哪个位置，j -> 这个位置的哪个颜色

    • dp[i][0]：粉刷i位置的时候，最后一个位置刷上红色，此时的最小花费
    • dp[i][1]：粉刷i位置的时候，最后一个位置刷上蓝色，此时的最小花费
    • dp[i][2]：粉刷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]
      

  • 初始化：dp[0][0] = dp[0][1] = dp[0][2] = 0

  • 确定填表顺序：从左往右，一次填写三个表

  • 确定返回值：min(dp[n][0], min(dp[n][1], dp[n][2]))

3.代码实现

int minCost(vector<vector<int>>& costs) 
{int n = costs.size();vector<vector<int>> dp(n + 1, vector<int>(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]));
}