动态规划之简单多状态 dp 问题（上）

按摩师

题目：按摩师

思路

• 状态表示：dp[i]表示选到i位置时，此时的最长预约时间；在nums[i]位置我们有两种方法，选或者不选；我们定义两个状态数组，f和 g：
  • 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])

C++代码

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

打家劫舍 II

题目：打家劫舍 II

思路：

通过分类讨论，将一个环形问题转化为一个打家劫舍1

原数组[0, 1, 2, n - 2, n - 1]
当第一个位置偷的时候，即1和n - 1 不能偷，我们对[2, n - 2]做一次打家劫舍1问题
当第一个位置不偷的时候，即1不能偷，我们对[1, n - 1]做一次打家劫舍1问题

• 状态表示：

  • 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])

C++代码

class Solution 
{
public:int rob(vector<int>& nums) {int n = nums.size();return max(_rob(nums, 2, n - 2) + nums[0], _rob(nums, 1, n - 1));}int _rob(vector<int>& nums, int begin, int end){if(begin > end) return 0;int n = nums.size();vector<int> f(n);auto g = f;f[begin] = nums[begin];for(int i = begin + 1; i <= end; i++){f[i] = g[i - 1] + nums[i];g[i] = max(f[i - 1], g[i - 1]);}return max(f[end], g[end]);}
};

删除并获得点数

题目： 删除并获得点数

思路：

将每个数字的出现的和记录在 arr数组中，然后在 arr数组上应用打家劫舍1的思路

• 状态表示：

  • 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])

C++代码

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

粉刷房子

题目：粉刷房子

思路：

• 状态表示：
  • dp[i][0] 表示：粉刷到i 位置时，粉刷红色，此时的最小花费；
  • dp[i][1] 表示：粉刷到i 位置时，粉刷蓝色，此时的最小花费；
  • dp[i][2] 表示：粉刷到i 位置时，粉刷绿色，此时的最小花费；
• 状态转移方程：
  • dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + cost[i][0]
  • dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + cost[i][1]
  • dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + cost[i][2]
• 初始化：
  • f[0] = nums[0]
  • g[0] = 0
• 填表顺序：三个表从左向右一起填写
• 返回值： min(dp[n][0], min(dp[n][1], dp[n][2]))

C++代码

class Solution 
{
public: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][1], dp[i - 1][0]) + costs[i - 1][2];}return min(dp[n][0], min(dp[n][1], dp[n][2]));}
};