题目
解法：区间dp
这是道经典的区间动态规划解决博弈问题。关键在于理解Alice和Bob的两种策略反应到dp的决策实际上是一样的
class Solution:def stoneGameVII(self, stones: List[int]) -> int:def dfs(l,r):if l==r:return 0if memo[l][r]:return memo[l][r]# no matter who's turn for current resursion', the optimal decision is the same# 1. if currently is Alice turn, since Alice want to maximum the difference, for current turn, Alice also want to maximize the difference# 2. if currently is Bob turn, since Bob want to minimize the difference, so he would want to maximize the current gain so the total difference will be minimizedmemo[l][r]= max(prefix_sum[r]-prefix_sum[l+1]-dfs(l+1,r),prefix_sum[r-1]-prefix_sum[l]-dfs(l,r-1))return memo[l][r]prefix_sum = [0]tmp = 0for stone in stones:tmp += stoneprefix_sum.append(tmp)n = len(stones)memo = [[0]*(n+1) for _ in range(n+1)]return dfs(0,len(stones))