动态规划之多状态问题1

题目解析：

也就是给一个预约数组，选择一些数字，让其总和最大，但不能选择相邻的两个数字

算法原理：

依旧可以根据经验+题目

以dp[i]位置结尾时，巴拉巴拉

根据题目要求补充完整，dp[i]：选择到i位置时，此时的最长预约时长

此时在分析，选择到i位置时i位置是不是有两种状态，一种是选i，一种是不选i

也就是说，你选择完前面的数，从0/1/2/3一直到i这个位置时，此时你面临i选还是不选

所以第i位置的状态又可以细分

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

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

状态转移方程：

f[i]：如何想？f[i]是选择到i位置时，必选的时候的最长预约时长，那是不是证明前面的最长预约时长+num[i]，那前面的最长预约时长如何找？这里由于选择了i就不能选i-1，所以我们要找不选i-1的最长时长，那不就是g[i-1]

所以f[i]=g[i-1]+nums[i];

那g[i]：怎么想？g[i]是选择到i位置时，i不选的最长预约时长，你不选i，那前面就可以选择i-1或者不选i-1，所以你要在f[i-1]和g[i-1]之间选择最大的那一个

 初始化：

根据状态表示很容易得到

填表顺序：

当然是从左往右

返回值：

 

代码编写 ：