Posted on 2023-07-28 17:37
Uriel 閱讀(60)
評論(0) 編輯 收藏 引用 所屬分類:
DP 、
遞歸 & 分治 、
閑來無事重切Leet Code
一個數列，每個值代表score，兩個player每次可以從數列頭or尾選一個數，問最后誰的總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