长春公司做网站找哪个公司好,东营招标建设信息网,开源门户网站建设方案,网站优化公司上海【问题描述】
一个有名的按摩师会收到源源不断的预约请求#xff0c;每个预约都可以选择接或不接。在每次预约服务之间要有休息时间#xff0c;因此她不能接受相邻的预约。给定一个预约请求序列#xff0c;替按摩师找到最优的预约集合#xff08;总预约时间最长#xff0…【问题描述】
一个有名的按摩师会收到源源不断的预约请求每个预约都可以选择接或不接。在每次预约服务之间要有休息时间因此她不能接受相邻的预约。给定一个预约请求序列替按摩师找到最优的预约集合总预约时间最长返回总的分钟数。注意本题相对原题稍作改动示例 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] 表示区间 [0i] 里接受预约请求并且下标为 i 的这一天不接受预约的最大时长dp[i][1] 表示区间 [0i] 里接受预约请求并且下标为 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]区间 [0i] 里接受预约请求的最大时长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-cn.com/problems/the-masseuse-lcci/solution/dong-tai-gui-hua-by-liweiwei1419-8/
