[Leedcode][JAVA][按摩师][动态规划]

【问题描述】

一个有名的按摩师会收到源源不断的预约请求，每个预约都可以选择接或不接。在每次预约服务之间要有休息时间，因此她不能接受相邻的预约。给定一个预约请求序列，替按摩师找到最优的预约集合（总预约时间最长），返回总的分钟数。注意：本题相对原题稍作改动示例 1：输入： [1,2,3,1]输出： 4解释： 选择 1 号预约和 3 号预约，总时长 = 1 + 3 = 4。示例 2：输入： [2,7,9,3,1]输出： 12解释： 选择 1 号预约、 3 号预约和 5 号预约，总时长 = 2 + 9 + 1 = 12。示例 3：输入： [2,1,4,5,3,1,1,3]输出： 12解释： 选择 1 号预约、 3 号预约、 5 号预约和 8 号预约，总时长 = 2 + 4 + 3 + 3 = 12。

【解答思路】

1. 动态规划 二维状态变量 由前往后 想清楚每一步

时间复杂度：O(N) 空间复杂度：O(N)

设计状态 dp[i][0] 表示：区间 [0，i] 里接受预约请求，并且下标为 i 的这一天不接受预约的最大时长；dp[i][1] 表示：区间 [0，i] 里接受预约请求，并且下标为 i 的这一天接受预约的最大时长。 状态转移方程 今天不接受预约：或者是昨天不接受预约，或者是昨天接受了预约，取二者最大值，即：dp[i][0] = max(dp[i - 1][0], dp[i - 1][1])；今天接受预约：只需要从昨天不接受预约转移而来，加上今天的时常，即：dp[i][1] = dp[i - 1][0] + nums[i]。

3.初始化

dp[0][0] = 0 与 dp[0][1] = nums[0]；

public int massage(int[] nums) {int len = nums.length;if (len == 0) {return 0;}if (len == 1) {return nums[0];}// dp[i][0]：区间 [0, i] 里接受预约请求，并且下标为 i 的这一天不接受预约的最大时长// dp[i][1]：区间 [0, i] 里接受预约请求，并且下标为 i 的这一天接受预约的最大时长int[][] dp = new int[len][2];dp[0][0] = 0;dp[0][1] = nums[0];for (int i = 1; i < len; i++) {dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1]);dp[i][1] = dp[i - 1][0] + nums[i];}return Math.max(dp[len - 1][0], dp[len - 1][1]);}

优化：状态数组多设置一行，以避免对极端用例进行讨论

public class Solution {public int massage(int[] nums) {int len = nums.length;// dp 数组多设置一行，相应地定义就要改变，遍历的一些细节也要相应改变// dp[i][0]：区间 [0, i) 里接受预约请求，并且下标为 i 的这一天不接受预约的最大时长// dp[i][1]：区间 [0, i) 里接受预约请求，并且下标为 i 的这一天接受预约的最大时长int[][] dp = new int[len + 1][2];// 注意：外层循环从 1 到 =len，相对 dp 数组而言，引用到 nums 数组的时候就要 -1for (int i = 1; i <= len; i++) {dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1]);dp[i][1] = dp[i - 1][0] + nums[i - 1];}return Math.max(dp[len][0], dp[len][1]);}}

优化 [滚动数组] 三个变量 时间复杂度：O(N) 空间复杂度：O(1)

public class Solution {public int massage(int[] nums) {int len = nums.length;if (len == 0) {return 0;}if (len == 1) {return nums[0];}// dp[i & 1][0]：区间 [0, i] 里接受预约请求，并且下标为 i 的这一天不接受预约的最大时长// dp[i & 1][1]：区间 [0, i] 里接受预约请求，并且下标为 i 的这一天接受预约的最大时长int[][] dp = new int[2][2];dp[0][0] = 0;dp[0][1] = nums[0];for (int i = 1; i < len; i++) {dp[i & 1][0] = Math.max(dp[(i - 1) & 1][0], dp[(i - 1) & 1][1]);dp[i & 1][1] = dp[(i - 1) & 1][0] + nums[i];}return Math.max(dp[(len - 1) & 1][0], dp[(len - 1) & 1][1]);}}

​###### 2. 动态规划 一维状态变量 由前往后 想清楚每一步

时间复杂度：O(N) 空间复杂度：O(N)

public int massage(int[] nums) {int len = nums.length;if (len == 0) {return 0;}if (len == 1) {return nums[0];}// dp[i]：区间 [0, i] 里接受预约请求的最大时长int[] dp = new int[len];//初始化状态dp[0] = nums[0];dp[1] = Math.max(nums[0], nums[1]);for (int i = 2; i < len; i++) {// 今天在选与不选中，选择一个最优的dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);}return dp[len - 1];}

优化 [滚动数组] 三个变量 时间复杂度：O(N) 空间复杂度：O(1)

class Solution {public int massage(int[] nums) {int len = nums.length;if (len == 0) {return 0;}if (len == 1) {return nums[0];}// dp[i % 3]：区间 [0，i] 里接受预约请求的最大时长int[] dp = new int[3];dp[0] = nums[0];dp[1] = Math.max(nums[0], nums[1]);for (int i = 2; i < len; i++) {// 今天在选与不选中，选择一个最优的dp[i % 3] = Math.max(dp[(i - 1) % 3], dp[(i - 2) % 3] + nums[i]);}return dp[(len - 1) % 3];}}

【总结】

1.动态规划流程

第 1 步：设计状态第 2 步：状态转移方程第 3 步：考虑初始化第 4 步：考虑输出第 5 步：考虑是否可以状态压缩

2.动态规划 自底向上 状态转移

[一般编程] 自顶向下

[记忆化递归」随时可能面对新问题

参考链接：https://leetcode-/problems/the-masseuse-lcci/solution/dong-tai-gui-hua-by-liweiwei1419-8/