【动态规划专栏】专题三：简单多状态dp--------1.按摩师

题目来源

本题来源为：

Leetcode 17.16按摩师

题目描述

一个有名的按摩师会收到源源不断的预约请求，每个预约都可以选择接或不接。在每次预约服务之间要有休息时间，因此她不能接受相邻的预约。给定一个预约请求序列，替按摩师找到最优的预约集合（总预约时间最长），返回总的分钟数。

注意：本题相对原题稍作改动

算法原理

1.状态表示

经验+题目要求

但是还要在细化一下：（在i位置时会有两种情况，选还是不选）

对于本题而言就是：

f[i]表示：选择到i位置时，nums[i]必选，此时的最长预约时长

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

2.状态转移方程

在分析状态转移方程之前，首先要分两种情况：

第一种情况，到i位置时选择预约，那么i-1位置就不能预约；i-1位置不能预约，看状态表示，就是g[i-1]

因此：

第一种情况，到i位置时不预约，那么i-1位置就有两种情况，预约或者不预约；i-1位置不能预约，看状态表示，就是g[i-1]，预约就是f[i-1],最后要取两者的最大值，因为走到i位置的时候，说明i-1位置是已经拿到最长时间过来的。

因此：

所以我们的状态转移方程为：

因此状态方程为：

f[i]=g[i-1]+nums[i];
 g[i]=max(f[i-1],g[i-1]);

3.初始化

只有在0位置会发生越界，因此初始化0位置即可。

4.填表顺序

从左往右，两个表同时填

5.返回值

返回：

代码实现

动态规划的代码基本就是固定的四步：

1.创建dp表
2.初始化
3.填表
4.返回值

本题完整代码实现：

时间复杂度：O(N)

空间复杂度：O(N)