[LeetCode]486. Predict the Winner (Medium) Python3-2023.07.28
Posted on 2023-07-28 17:37 Uriel 閱讀(47) 評論(0) 編輯 收藏 引用 所屬分類: DP 、遞歸 & 分治 、閑來無事重切Leet Code一個數(shù)列,每個值代表score,兩個player每次可以從數(shù)列頭or尾選一個數(shù),問最后誰的總score最高,遞歸+DP,參考了Discussion -> https://leetcode.com/problems/predict-the-winner/solutions/3826270/python3-solution/
1 #486
2 #Runtime: 41 ms (Beats 96.36%)
3 #Memory: 16.7 MB (Beats 19.78%)
4
5 class Solution:
6 def PredictTheWinner(self, nums: List[int]) -> bool:
7 n = len(nums)
8 @lru_cache(None)
9 def dp(i, j):
10 return 0 if i > j else max(-dp(i + 1, j) + nums[i], -dp(i, j - 1) + nums[j])
11
12 return dp(0, n -1) >= 0
2 #Runtime: 41 ms (Beats 96.36%)
3 #Memory: 16.7 MB (Beats 19.78%)
4
5 class Solution:
6 def PredictTheWinner(self, nums: List[int]) -> bool:
7 n = len(nums)
8 @lru_cache(None)
9 def dp(i, j):
10 return 0 if i > j else max(-dp(i + 1, j) + nums[i], -dp(i, j - 1) + nums[j])
11
12 return dp(0, n -1) >= 0