leetcode 面試題 17.16 按摩師 php動态規劃解決 滾動變量優化

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

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

示例 1：輸入： [1,2,3,1]    輸出： 4

解釋： 選擇 1 号預約和 3 号預約，總時長 = 1 + 3 = 4。

作者：FlagMain

連結：https://leetcode-cn.com/problems/the-masseuse-lcci/solution/1716-an-mo-shi-phpdong-tai-gui-hua-jie-jue-gun-don/

解題思路

動态規劃解決

把每次處理的目前元素當成最後一個元素處理。目前元素前一位的處理結果已知，隻需要判斷目前處理規則 加前一次已知結果

每次處理有兩種可能，這次接受 和 這次不接受

是以設定記錄每次處理的兩種結果 $dp[i][0]不接受 和 $dp[i][1]接受 來代表兩種情況選擇的總數

$dp[i][0]不接受 那上次肯定沒有接受預約或上次接受了預約 是以我們取值為 已知的 上次處理兩種情況的最大值

$dp[i][1]接受 那上次肯定沒有接受預約 是以取值為 已知的 上次處理沒有接受預約的結果

初始化第1天的選擇結果

$dp[0][0] = 0; //下标為 i 的這一天不接受預約的最大時長

$dp[0][1] = $nums[0]; //下标為 i 的這一天接受預約的最大時長

// 第二行 -- 左面是不選擇(取上一次結果中最大值)，右面是選擇(選擇上次結果左邊值)

//   1,       2,       3,       1

// 0   1    1   2    2   4    4   3

//   1        2        4        4

// 優化後方法 massage3()

class Solution {

    /**
     * @param $nums
     * @return int|mixed
     */
    function massage($nums) {
        // 時間複雜度 O(n)
        // 空間複雜度 O(2n)
        $count = count($nums);
        if ( $count == 0 ) return 0;
        if ( $count == 1 ) return $nums[0];

        // 初始化第1天
        $dp[0][0] = 0;        //第一天 如果不接受 那就是0
        $dp[0][1] = $nums[0]; //第一天 如果接受 那就是第一個元素值
        // 第一天情況已經分别已知，去處理剩餘
        for ($i = 1; $i < $count; $i++) {
            //不接受：上次沒有接受預約，或上次接受了預約。取最大值即：max($dp[$i - 1][0], $dp[$i - 1][1]);
            $dp[$i][0] = max($dp[$i - 1][0], $dp[$i - 1][1]);
            //接受：上次肯定沒有接受預約，加上這次的值即：dp[i - 1][0] + nums[i]
            $dp[$i][1] = $dp[$i - 1][0] + $nums[$i];
        }
        // 傳回最終結果的最大值
        return max($dp[$count - 1][0], $dp[$count - 1][1]);
    }
    
    // -----------------------------------------------------------------------
    
    
    // 優化 function massage()
    // 根據massage()基于二維數組的處理 優化為一維數組的處理 優化空間複雜度 O(n)
    // 目前處理的結果是 上次的結果值 和 上上次的結果值加上目前值 的最大值
    function massage2($nums) {
        $count = count($nums);
        if ( $count == 0 ) return 0;
        if ( $count == 1 ) return $nums[0];

        // 設定前兩次的最大結果
        $dp[0] = $nums[0];
        $dp[1] = max($nums[0],$nums[1]);
        // 處理剩餘
        for ($i = 2; $i < $count; $i++) {
            // 上次的結果值 和 上上次的結果值加上目前值 的最大值
            $dp[$i] = max($dp[$i - 1], $dp[$i - 2] + $nums[$i]);
        }
        return array_pop($dp);
    }
    
    // -----------------------------------------------------------------------


    // 優化 function massage()
    // 滾動變量處理 優化空間複雜度 O(1)
    function massage3($nums) {
        $count = count($nums);
        if ( $count == 0 ) return 0;
        if ( $count == 1 ) return $nums[0];

        // 設定第一次各情況值
        $a = 0;
        $b = $nums[0];
        // 處理剩餘
        for ($i = 1; $i < $count; $i++) {
            // 獲得不選擇時 最優結果
            $tmp1 = $a > $b ? $a : $b;
            // 擷取選擇時 結果
            $tmp2 = $a + $nums[$i];
            $a = $tmp1;
            $b = $tmp2;
        }
        // 傳回最優值
        return $a > $b ? $a : $b;
    }
}

$arr = [1,2,3,1];
$arr = [2,1,4,5,3,1,1,3];
print_r( (new Solution())->massage( $arr ) );