Posted on 2023-07-28 17:37
Uriel 阅读(26)
评论(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