【动态规划】打家劫舍类问题_动态规划打家劫舍问题

一、按摩师

17.16. 按摩师

题目描述：

题目分析：

1、状态表示

每个预约都只会有两种选择，即选或不选。因此我们可以用

• dp[i][0] 表示不选择第 i 个预约时，最长的预约时长
• dp[i][1] 表示选择第 i 个预约时，最长的预约时长

2、状态转移方程

对于dp[i][0] ：

• 如果我们选择了第 i 个预约，那么第 i-1 次预约就一定不会选择，这时我们只需要知道不选第 i-1 次预约时的最长预约时长即可，即 dp[i-1][0] 的值，再加上 num[i] 即可。可得递推公式就为：

dp[i][1]=dp[i-1][0]+nums[i]

对于dp[i][1] ：

• 如果我们不选择第 i 个预约，那么第 i-1 次预约就可以被选择，当然也可以不选，这时我们只需要知道选或不选第 i-1 次预约时分别的最长预约时长即可，即 dp[i-1][0] 与 dp[i-1][0] 的值，取这两个中的最大值即可。可得递推公式就为：

dp[i][0]=Mat