动态规划问题 -- 多状态模型第一题（按摩师）
目录
- 动态规划分析问题五步曲
- 多状态常用的分析方法（经验）
- 题目概述
- 代码编写
- 多状态模型题单（后续会一一讲解）
动态规划分析问题五步曲
不清楚动态规划分析问题是哪关键的五步的少年们可以移步到
链接: 动态规划算法基础
这篇文章非常详细的介绍了动态规划算法是如何分析和解决问题的
多状态常用的分析方法（经验）
在我们分析第i个位置时，发现第i个位置可能有不同情况需要分类讨论的
这个时候一个简单dp表可解决不了问题，需要N个dp表解决问题（N为分类讨论的数目）
题目概述
链接: 按摩师
- 状态表示（题目要求+自己的经验）
dp[i] : 表示服务到第i个位置时预约时间最长的分钟数（暂定）
- 状态转移方程推导
分析dp[i]个位置 ： 发现第i个位置出现了 预约和不预约 两种情况，所以我们上述定义的状态表示有问题，应该要表明dp[i]位置是以预约结尾还是以不预约结尾。
所以我们需要两个状态表 ：
visit[i]表示以i为结尾，并且visit[i]位置预约按摩师的最大预约时间
novisit[i]表示以i为结尾，但是novisit[i]位置不预约按摩师的最大预约时间
现在来分情况讨论状态转移方程式
- 填visit表，若第i个位置以预约结尾，则第i-1个位置必须不预约
- 填novisit表，若第i个位置以不预约结尾，则第i-1个位置可以以不预约结尾，也可以以预约结尾
得出状态转态方程：
- 初始化（防止越界+结合状态表示初始化）
根据状态转移方程式，只有i == 0的时候会越界，所以我们初始化visit[0] 和 novisit[0] 即可
根据状态表示，令visit[0] = nums[0] , novisit[0] = 0;
- 填表顺序（分析要填i位置前一个依赖状态的位置）
本题显然是从左到右
- 返回值（由题目要求来）
本题我们分类讨论了，理应返回多种情况的最大值return max(visit[m-1], novisit[m-1])
代码编写
分析了动态规划五步曲后就可以写出优雅的代码了
int massage(vector<int>& nums) { int m = nums.size(); if(m == 0) return 0; vector<int> visit(m); vector<int> novisit(m); visit[0] = nums[0]; for(int i = 1 ; i < m ; i++) { visit[i] = novisit[i-1] + nums[i]; novisit[i] = max(visit[i-1],novisit[i-1]); } return max(visit[m-1],novisit[m-1]); }多状态模型题单（后续会一一讲解）
链接: 打家劫舍
链接: 打家劫舍II
链接: 删除并获得点数
链接: 粉刷房子
链接: 买股票的最佳时期II
链接: 买股票的最佳时期含冷冻期
链接: 买股票的最佳时期含手续费
少年今天的你又进步了一点点唷，明天继续加油吧
