简单多状态dp第一弹 leetcode -面试题17.16.按摩师 -213.打家劫舍II

a​​​​​​​面试题 17.16. 按摩师

按摩师

题目:

分析:

使用动态规划解决

状态表示:

dp[i] 表示：选择到 i 位置时，此时的最长预约时长。

但是我们这个题在 i 位置的时候，会面临 选择 或者 不选择 两种抉择，所依赖的状态需要
细分：

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

源码：

class Solution {
public:int massage(vector<int>& nums) {int n=nums.size();vector<int>f(n+1);//选vector<int>g(n+1);//不选if(n==0){return 0;}f[0]=nums[0];for(int i=1;i<n;i++){f[i]=g[i-1]+nums[i];g[i]=max(g[i-1],f[i-1]);}return max(f[n-1],g[n-1]);}
};

---

213. 打家劫舍 II

打家劫舍II

题目:

分析:

使用动态规划解决

1.偷第一个房屋时的最大金额 x ，此时不能偷最后一个房子，因此就是偷 [0, n - 2] 区间
的房子；

2.不偷第一个房屋时的最大金额 y ，此时可以偷最后一个房子，因此就是偷 [1, n - 1] 区
间的房子；

两种情况下的「最大值」，就是最终的结果。(做两次打家劫舍I)

代码:

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