动态规划 —— dp问题-按摩师

1. 按摩师

题目链接： 面试题 17.16. 按摩师 - 力扣（LeetCode）

https://leetcode.cn/problems/the-masseuse-lcci/description/

2. 算法原理

状态表示：以某一个位置为结尾或者以某一个位置为起点 dp[i]表示：选择到i位置的时候，此时的最长预约时长分两种情况： 1.f[i]表示：选择到i位置的时候，当前位置nums[i]必选，此时的最长预约时长 2.g[i]表示：选择到i位置的时候，当前位置nums[i]不选，此时的最长预约时长

2. 状态转移方程 根据最近的一步来划分问题： 到达dp[i][j]有两种情况： 1. f[i]=g[i-1] + nums[i]

2. g[i]：a. 当选择i-1的位置时：f[i-1] b.当不选择i-1的位置时：g[i-1] g[i]=max(f[i-1],g[i-1])

3. 初始化 ：把dp表填满不越界，让后面的填表可以顺利进行 本题初始化为：f[0]=nums[0] g[0]在vector填表的时候默认为0

4. 填表顺序 本题的填表顺序是：从左往右，两个表一起填

5. 返回值 ：题目要求 + 状态表示 本题的返回值是：max(f[n-1],g[n-1])

3.代码

动态规划的固定四步骤：1. 创建一个dp表 2. 在填表之前初始化 3. 填表（填表方法：状态转移方程） 4. 确定返回值

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

完结撒花~