Leetcode算法题：按摩师（动态规划java）

Leetcode算法题：按摩师（动态规划java）

按摩师## 标题
题目描述：一个有名的按摩师会收到源源不断的预约请求，每个预约都可以选择接或不接。在每次预约服务之间要有休息时间，因此她不能接受相邻的预约。给定一个预约请求序列，替按摩师找到最优的预约集合（总预约时间最长），返回总的分钟数。
解题方法：动态规划

解题思路:

• 第一步

：开一个二维数组dp[n][2]
由于当前这一天有按摩师有两种选择：
（1）接预约；
（2）不接预约。但根据题意，今天是否接预约，是受到昨天影响的。为了消除这种影响，我们在状态数组要设置这个维度。

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]。

• 第三步：初始条件和边界情况

dp[0][0]=0;
dp[0][1]=nums[0];

• 第四步：计算顺序

dp[0][1] dp[1][1]…

代码

class Solution {public int massage(int[] nums) {//开一个二维数组，第二维度解决其后效性，通常情况下，容易受到其他因素干扰的可以增加第二个维度int n=nums.length;        int[][]dp=new int[n][2];//开一个二维数组；if(n==0)return 0;if(n==1)return nums[0];dp[0][0]=0;dp[0][1]=nums[0];for(int i=1;i<n;i++){//第i个预约不接受dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]);//第i个预约接受dp[i][1]=dp[i-1][0]+nums[i];}return(Math.max(dp[n-1][1],dp[n-1][0]));}
}

下面总结一下动态规划的基本步骤：

这是一道简单的动态规划问题做出的总结！谢谢大家阅读到这里！