玩遊戲也可以用DP ? 石頭遊戲 I 的最佳策略_Leetcode #877

題目敘述

給定一個piles陣列，裡面對應到每堆石頭的數量。

Alice 和 Bob玩輪流取石頭的遊戲，總共有n堆石頭，每堆的石頭數量有多有少。

Alice先取，接著Bob，反覆交替，每回合輪到的人可以從當下的第一堆或者最後一堆，拿走那堆對應的石頭。

最後比誰拿到的石頭總數量比較多就獲勝。

請問，如果最後Alice可以贏，返回True；如果不行，返回False。

題目額外保證，不會有平手的情況發生。

題目的原文敘述

約束條件

Constraints:

• 2 <= piles.length <= 500

每堆最少有兩顆石頭，最多有500顆石頭。

• piles.length is even.

總共有偶數堆。

• 1 <= piles[i] <= 500

最少一堆，最多500堆。

• sum(piles[i]) is odd.

全部石頭總數目是奇數。

演算法 區間DP 搭配 min/Max

區間DP定義

取石頭的區間可以用區間DP來描述。

DP[left, right] = 從left ~ right 區間內，我方取的石頭 - 對手取的石頭的最大值。

相當於最大化我方取的石頭數目，最小化對手取的石頭數目。

通則怎麼想呢?

題目說，每回合輪到的人可以取當下的第一堆或者最後一堆。

如果取當下的第一堆，那麼對手剩下[left+1, right]的區間可以選擇，對手的情況相當於DP[left+1, right]。

如果取當下的最後一堆，那麼對手剩下[left, right-1]的區間可以選擇，對手的情況相當於DP[left, right-1]。

因為我們要的是採取最佳策略，白話的說，就是我方取的數目領先對手越多越好。

因此，當下的取石頭的最佳策略可以這樣表達

Max(取第一堆，取最後一堆)
= Max( piles[left] - DP[left+1, right], piles[right] - DP[left, right-1] )

遞迴的終止條件(也可以說初始條件)是什麼呢?

就是取到剩下一堆的時候，這時候left =right

DP[left, right] 且 left 剛好等於right
= piles[left]

OK，現在DP的定義、通則、終止條件都有了!

寫成對應的DP程式碼即可。

最佳策略取石頭的區間DP程式碼

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        
        # DP Table
        memo = {}

        def take(left, right):
            
            # Look-up DP Table
            if (left, right) in memo:
                return memo[(left, right)]

            # Base case
            if left == right:
                return piles[left]

            # General cases
            # Option_1
            take_first_pile = piles[left] - take(left+1, right)

            # Option_2
            take_last_pile = piles[right] - take(left, right-1)

            memo[(left, right)] = max( take_first_pile,  take_last_pile)
            return memo[(left, right)]
        #================================
        return take(0, len(piles)-1) > 0

複雜度分析

令 n = len(piles)

時間複雜度

DP狀態數目依賴於(left, right)，二維DP的狀態總數為O(n^2)。

每個狀態在常數時間O(1)可以求出最佳解。

總共所需時間為O(n^2) * O(1) = O( n^2 )。

空間複雜度

DP table需要儲存 O(n^2)個狀態，另外DP遞迴的最大深度也是O(n^2)

總共所需空間維O(n^2)。

關鍵知識點

從題目的敘述和範例觀察，最佳選擇策略可以用區間DP描述。

DP的通則可以由選擇的分支推導出來。

當下的取石頭的最佳策略可以這樣表達

Max(取第一堆，取最後一堆)

= Max( piles[left] - DP[left+1, right], piles[right] - DP[left, right-1] )

Reference

[1] Stone Game - LeetCode