【动态规划】11简单多状态 dp 问题_按摩师_C++（easy）

题目链接：leetcode按摩师

---

目录

题目解析：

算法原理

1.状态表示

2.状态转移方程

3.初始化

4.填表顺序

5.返回值

编写代码

---

题目解析：

题目让我们求按摩师找到最优的预约集合（总预约时间最长）

由题可得：

按摩师每个预约都可以选择接或不接，并且她不能接受相邻的预约

我们以示例一分析：

所以这里的最长预约时长是4

---

算法原理:

1.状态表示

先创建一个dp表

首先先思考dp表里面的值所表示的含义（是什么？）

因为我们这里的每个位置可以选或者不选，

所以这里我们一个位置就有两种状态

这里就要创建两个dp表来表示这两种状态：

f[i]表示到i位置选，此时到i位置的最长预约时长；

g[i]表示到i位置不选，此时到i位置的最长预约时长；

这种状态表示怎么来的？

1.经验+题目要求

用之前或者之后的状态，推导出dp[i]的值；

根据最近的最近的一步，来划分问题

经验：以i位置为结尾；

题目让我们求最长预约时长，且该位置可选可不选，

这里我们需要用两个表来同时表示这种状态；

2.状态转移方程

dp[i]等于什么？

因为i位置可选可不选，所有两种情况：

第一种情况：（i位置选）

那么i-1位置必然不选：

此时我们只要知道在i-1之前所得到的最长预约时长（g[i-1]）+i位置的时长(nums[i])

所以这种情况下的状态转移方程为：

dp[i]=f[i-1]+nums[i];

第二种情况：（i位置不选）

那么i-1位置可以选也可以不选，

这里会分两种情况：

情况a：（i-1选）

此时我们只要知道在i-1之前所得到的最长预约时长（f[i-1]）

所以这种情况下的状态转移方程为：

dp[i]=f[i-1];

情况b：（i-1不选）

此时我们只要知道在i-1之前所得到的最长预约时长（g[i-1]）

所以这种情况下的状态转移方程为：

dp[i]=g[i-1];

最后取a，b情况的最大值：min（f[i-1]，g[i-1]）

综上：

3.初始化

(保证填表的时候不越界)

由状态转移方程得：

我们在f[0]和g[0]会越界，所以需要把这两个位置初始化；

当第一个位置选，那么它的最长预约时长f[0]为该位置的时长（f[0]=nums[0]）；

当第一个位置不选，那么它的最长预约时长g[0]为0（g[0]=0）；

4.填表顺序

（为了填写当前状态的时候，所需要的状态已经计算过了）

这里所需要的状态是：i-1

所以填表顺序：从左到右

5.返回值

（根据题目要求和状态表示）

综上分析：

最后一个位置可选可不选，所以返回这两个状态的最小值

返回值为：min(f[n-1],g[n-1]);

---

编写代码:

class Solution {
public:
    int massage(vector<int>& nums) {
        //1.创建dp表
        //2.初始化
        //3.填表
        //4.返回结果


        //边界问题
        if(nums.size()==0)
            return 0;

        int n=nums.size();
        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(g[i-1],f[i-1]);
        }

        return max(f[n-1],g[n-1]);


    }
};