一個(gè)數(shù)列，每個(gè)值代表score，兩個(gè)player每次可以從數(shù)列頭or尾選一個(gè)數(shù)，問(wèn)最后誰(shuí)的總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