面试题 17.16. 按摩师

#面试题 17.16. 按摩师

题目描述

解题思路
看到这个题都没什么思路，看了评论之后发现是简单动态规划问题，嗷我真的太菜了，在这里补充一下动态规划的知识吧。

动规解题的一般思路
1、 将原问题分解为子问题(开头已经介绍了怎么分解) (注意:1,子问题与原问题形式相同或类似,只是问题规模变小了,从而变简单了; 2,子问题一旦求出就要保存下来,保证每个子问题只求解一遍)
2、确定状态(状态:在动规解题中,我们将和子问题相关的各个变量的一组取值,称之为一个"状态",一个状态对应一个或多个子问题所谓的在某个状态的值,这个就是状态所对应的子问题的解,所有状态的集合称为"状态空间".我的理解就是状态就是某个问题某组变量,状态空间就是该问题的所有组变量) 另外:整个问题的时间复杂度就是状态数目乘以每个状态所需要的时间
3、确定一些初始状态(边界条件)的值 (这个视情况而定,千万别以为就是最简单的那个子问题解,上面只是例子,真正实践动规千变万化)
4、确定状态转移方程 (这一步和第三步是最关键的 记住"人人为我"递推,由已知推未知)
适合使用动规求解的问题:
1,问题具有最优子结构
2,无后效性 说的花里胡哨的,其实一般遇到求最优解问题一般适合使用动态规划

对于这道题，要得到最大时长，就是最优化问题，而且不要求保存最优时候的序列，而且最后预约时长是前面的很多个小问题分解来的，前面的最优值才能得到后面的最优值。
第n个预约的最大时长dp[n]：1. 如果我们接第n个预约的话，由于相邻的预约不能接，所以dp[n] = dp[n - 2] + nums[n]（即等于到第n-2个预约的最大时长 + 第n个预约的时长）； 2. 反之如果我们不接第n个预约的话，那么dp[n] = d[n - 1]（即等于到第n - 1个预约的最大时长）。
于是，我们得到了状态转移方程：dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
接下来代码部分就简单了，照着状态转移方程递推。

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

提交结果：

另外，这道题还能再对空间进行优化，每次只保存dp数组前两个值。

public int massage(int[] nums) {        
	int n = nums.length;         
	int pre1 = 0,pre2 = 0,max = 0;  //pre1位置上的前一个，pre2前两个
	for (int i = 0; i < n; i++) {            
		max = Math.max(pre2+nums[i], pre1);            
		pre2 = pre1;            
		pre1 = max;        
	}        
	return pre1;    
}

相似题目
本题和 198. 打家劫舍 是一模一样的重题
小偷系列一共三道都可以做做：198. 打家劫舍、213. 打家劫舍II、337 打家劫舍III