頭腦風暴：按摩師

題目

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

示例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 數組的含義：

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 數組：如果第一天不接受預約，那麼 dp[0][0] = 0, 如果第一天接受預約 dp[0][1] = nums[0];

代碼實作

class Solution {
    public int massage(int[] nums) {
        int len = nums.length;
        if(len == 0){
            return 0;
        }

        if(len == 1){
            return nums[0];
        }

        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]);
    }
}      

最後

• 時間複雜度：O(n)，其中 n 為預約的個數。
• 空間複雜度：O(1)，隻需要常數的空間存放若幹變量。

1. 關注公衆号---​​HelloWorld傑少​​