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]);}};
