Leetcode # 486. Predict the Winner

https://leetcode.com/problems/predict-the-winner

Solution (Recursive)

Time Complexity: O(2 ** len(nums))
Space Complexity: O(len(nums))
(The input and output generally do not count towards the space complexity.)

class Solution:
  def PredictTheWinner(self, nums: List[int]) -> bool:
    def predict_winner(nums):
      if len(nums) == 1:
        return nums[0]
      return max(nums[ 0] - predict_winner(nums[ 1:]), 
                 nums[-1] - predict_winner(nums[:-1]))
    return predict_winner(nums) >= 0

Solution (DP – Memoization (Top-Down))

在上一個 Solution 中存在著重複的計算

例：
nums = [1, 2, 3, 4, 5]
⇒ [1] + [2, 3, 4, 5] ⇒ [1] + ([2, 3, 4] + [5]) 
⇒ [1, 2, 3, 4] + [5] ⇒ ([1] + [2, 3, 4]) + [5] 

所以我們使用 Memoization 保存已計算過的結果

Time Complexity: O(len(nums) ** 2)
Space Complexity: O(len(nums) ** 2)
(The input and output generally do not count towards the space complexity.)

class Solution:
  def PredictTheWinner(self, nums: List[int]) -> bool:
    self.dp = {(i, i): nums[i] for i in range(len(nums))}
    def predict_winner(start, end):
      if (start, end) not in self.dp:
        result =  max(nums[start] - predict_winner(start + 1, end), 
                      nums[  end] - predict_winner(start, end - 1))
        self.dp[(start, end)] = result
      return self.dp[(start, end)]
    return predict_winner(0, len(nums) - 1) >= 0

Solution: Space-Optimized (Bottom-Up)

curr: dp[(0, k)], dp[(1, k + 1)], dp[(2, k + 2)], …, dp[(N – k – 1), (N – 1)]
next: dp[(0, k + 1)], dp[(1, k + 2)], dp[(2, k + 3)], …, dp[(N – k – 2 ), (N – 1)]

1. dp[(0, k + 1)] = max(num[k + 1] – dp[(0, k)], num[0] – dp[1, k + 1])
   ⇒ dp[(0, k)]dp[(0, k + 1)], dp[(1, k + 1)], dp[(2, k + 2)], …, dp[(N – k – 1), (N – 1)]
2. dp[(1, k + 2)] = max(num[k + 2] – dp[(1, k + 1)], num[1] – dp[2, k + 2])
   ⇒ dp[(0, k + 1)], dp[(1, k + 1)]dp[(1, k + 2)] , dp[(2, k + 2)], …, dp[(N – k – 1), (N – 1)]
3. …
4. dp[(0, k + 1)], dp[(1, k + 2)], dp[(2, k + 3)], …, dp[(N – k – 1), (N – 1)]dp[(N – k – 2 ), (N – 1)], dp[(N – k – 1), (N – 1)]

每次我們依序計算出一個 next 的新項目
就會有一個 curr 的項目不會再被使用
所以我們可以將該項目的空間讓給新項目
（最後每一輪結束時還會額外多出一個空間）

註：dp = [n for n in nums]nums[:]

Time Complexity: O(len(nums) ** 2)
Space Complexity: O(len(nums))
(The input and output generally do not count towards the space complexity.)

class Solution:
  def PredictTheWinner(self, nums: List[int]) -> bool:
    dp = nums[:]
    for l in range(1, len(nums)):
      for i in range(len(nums) - l):
        dp[i]=  max((nums[i]     - dp[i + 1]), 
                     nums[i + l] - dp[i])
    return dp[0] >= 0

Last Updated on 2023/08/16 by A1go