力扣刷题系列-面试题 17.16. 按摩师

题干题目分析代码实现

题干

原题链接

题目分析

本题是一道简单的动态规划，有点类似于力扣中的打家劫舍和爬楼梯因为不能接受相邻的预约，又要求出最大值，因此状态设计为当前总预约的最大值dp[i]，dp[i]只能是由dp[i-2]+nums[i]或者dp[i-1]得来，所以得出状态方程：

dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])

该算法从时间上看只需要遍历一次数组，所以时间复杂度为O(n)，状态数组也可以直接在原数组上修改，所以空间复杂度为O(1)

代码实现

class Solution { public int massage(int[] nums) { if(nums.length == 0){ return 0; } if(nums.length == 1){ return nums[0]; } nums[1] = Math.max(nums[0],nums[1]); for(int i = 2; i < nums.length; ++i){ nums[i] = Math.max(nums[i - 2] + nums[i], nums[i - 1]); } return nums[nums.length - 1]; } }