题目链接：

面试题 17.16. 按摩师 - 力扣（LeetCode）

1、状态表示

用两个dp表，分别表示到当前位置接受预约和不接受预约

f[i]：表示到 i 位置，接受预约的最优预约集合

g[i]：表示到 i 位置，不接受预约的最有预约集合

2、方程

若当前位置接受预约，那么当前位置的前一个位置（i-1）必然不接受预约，g[i-1]即为到前一个位置为止最优预约集合。方程为：f[i]=g[i-1]+nums[i] 

若当前位置不接受预约，那么当前位置的前一个位置可能接受预约（f[i-1]），也可能不接受预约（g[i-1]）；当前位置不接受预约，nums[i]直接忽略。方程为：g[i]=max(f[i-1],g[i-1])

3、初始化

接受预约状态表vector<int> f(n)的第一个位置f[0]表示0位置接受预约，因此f[0]=nums[0]

不接受预约状态表vector<int> g(n)的第一个位置g[0]表示0位置不接受预约，因此g[0]=0

4、填表顺序

后面的值与前面值有关，由左向右

5、返回值

最后一个位置不确定是接受还是不接受预约，选择f表与g表中较大的一个返回即可

代码实现：

class Solution {
public:int massage(vector<int>& nums) {int n=nums.size();if(n==0)    return 0;//当nums为空时单独处理，否则后续会出现非法访问的问题//if(n==1)    return nums[0];vector<int> f(n,0);auto g=f;f[0]=nums[0];g[0]=0;for(int i=1;i<n;i++){f[i]=g[i-1]+nums[i];g[i]=max(f[i-1],g[i-1]);//cout<<f[i]<<"  "<<g[i]<<endl;}int x=max(f[n-1],g[n-1]);return x;}
};