简朴多状态dp问题 + 总结（一）

按摩师

标题链接

题解

   1. 细节处理：标题是有没有客人的时间，所有n便是零时返回零
2. 状态表现：到达i位置时的最长预约时长
3. 状态转移方程：到达i位置的时间分为选或者不选，选的话，前一个位置就是不选，不选的话，前一个位置可以是不选或者是选中的最大值
  

代码

1. class Solution
2. {
3. public:
4.     int massage(vector<int>& nums)
5.     {
6.         int n = nums.size();
7.         if(n == 0) return 0;// 空数组是没有预约时间的
8.         vector<int> f(n);// 最后一个状态选
9.         vector<int> g(n);// 最后一个状态不选
10.         f[0] = nums[0];
11.         for(int i = 1;i < n;i++)
12.         {
13.             f[i] = g[i-1] + nums[i];
14.             g[i] = max(f[i-1],g[i-1]);
15.         }
16.         return max(g[n-1],f[n-1]);
17.     }
18. };

复制代码

打家劫舍II

标题链接

题解

   1. 这题的思路和按摩师几乎一模一样，只不外可以分为第一个位置偷和第一个位置不偷的环境，末了比力两种环境哪种的金额最大
2. 第一个位置偷的环境，那么末了一个位置和第二个位置都不能偷，在[2，n-2]内进行一次按摩师
第一个位置不偷的环境，在[1，n-1]区间内进行一次按摩师
  

代码

1. class Solution
2. {
3. public:
4.     int rob(vector<int>& nums)
5.     {
6.         int n = nums.size();
7.         if(n == 0) return 0;
8.         if(n == 1)
9.         {
10.             return nums[0];
11.         }
12.         if(n == 2)
13.         {
14.             return nums[0] > nums[1] ? nums[0] : nums[1];
15.         }
17.         vector<int> f(n);// 最后一个位置偷
18.         vector<int> g(n);// 最后一个位置不偷
20.         f[2] = nums[2],g[2] = 0;
21.         int x = 0,y = 0;
22.         // 第一个位置偷
23.         for(int i = 3;i < n-1;i++)
24.         {
25.             f[i] = g[i-1] + nums[i];
26.             g[i] = max(g[i-1],f[i-1]);
27.         }
28.         x = nums[0] + max(f[n-2],g[n-2]);
29.         // 第一个位置不偷
31.         f[1] = nums[1],g[1] = 0;
32.         for(int i = 2;i < n;i++)
33.         {
34.             f[i] = g[i-1] + nums[i];
35.             g[i] = max(g[i-1],f[i-1]);
36.         }
37.         y = max(f[n-1],g[n-1]);
38.         return max(x,y);
39.     }
40. };

复制代码

删除并获得点数

标题链接

题解

   1. 可以先将数组预处理为下标对应的数的所有和相加，这样可以转换为打家劫舍问题，排序后选了一个数，相邻的两个数不能选
2. 这样arr数组就可以写成打家劫舍问题的代码了
  

代码

1. class Solution
2. {
3. public:
4.     int arr[10001];
5.     int deleteAndEarn(vector<int>& nums)
6.     {
7.         // 怎么达到不遍历可以删除其他数达到最大值呢？
8.         // 可以转化为自己熟悉的打家劫舍问题
9.         int n = nums.size();
10.         int ans = 0;
11.         for(int i = 0;i < n;i++)
12.         {
13.             arr[nums[i]] += nums[i];
14.             ans = max(ans,nums[i]);
15.         }
16.         
17.         if(n == 0) return 0;
19.         vector<int> f(ans+1);
20.         vector<int> g(ans+1);
21.         f[0] = arr[0],g[0] = 0;
22.         for(int i = 1;i <= ans;i++)
23.         {
24.             f[i] = g[i-1] + arr[i];
25.             g[i] = max(f[i-1],g[i-1]);
26.         }
27.         return max(f[ans],g[ans]);
28.     }
29. };

复制代码

粉刷房子

标题链接

题解

   1. 红色是0，绿色是1，蓝色是2
2. 可以分解为3个一维的线性dp，末了一个位置选红色，那么前一个位置的状态是选绿色和黄色中的最小值
3. 同时填表，有三种颜色，n个房子，按线性dp的模式写
  

代码

1. class Solution
2. {
3. public:
4.     int minCost(vector<vector<int>>& costs)
5.     {
6.         int n = costs.size();
7.         vector<vector<int>> dp(n+1,vector<int>(3));// 0红 1绿 2蓝
8.         for(int i = 1;i < n+1;i++)
9.         {
10.             dp[i][0] = min(dp[i-1][1],dp[i-1][2]) + costs[i-1][0];
11.             dp[i][1] = min(dp[i-1][0],dp[i-1][2]) + costs[i-1][1];
12.             dp[i][2] = min(dp[i-1][1],dp[i-1][0]) + costs[i-1][2];
13.         }
14.         return min(min(dp[n][0],dp[n][1]),dp[n][2]);
15.     }
16. };

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。