面試題17.16.按摩師（動态規劃法）

題目描述

一個有名的按摩師會收到源源不斷的預約請求，每個預約都可以選擇接或不接。在每次預約服務之間要有休息時間，是以她不能接受相鄰的預約。給定一個預約請求序列，替按摩師找到最優的預約集合（總預約時間最長），傳回總的分鐘數。

注意：本題相對原題稍作改動

示例 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。

遞推式

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

代碼

package interview_17_16;

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

性能表現