网站建设外包怎么样6个好用的bt种子搜索引擎

f[i][M] 表示从位置i开始，取前X堆石子，其中1<=X<=2 * M 的石子最多个数。

f[i][M] 有如下转移，如果 i + 2 * M > n, 即可以将后面的石子全拿完，那么就全部拿完。

否则，枚举X，当前f[i][M] = max( sum(piels[i:]) - f[i+X][M']) 其中M' = max(i, M);

然后我们再用前缀和预处理优化：

class Solution:def stoneGameII(self, piles: List[int]) -> int:n = len(piles)s = [0] * (n + 1)for i in range(1, n + 1):s[i] = s[i - 1] + piles[i - 1]@lru_cache(None)def maxNum(start, M):if start + 2*M >= n: return s[n] - s[start]res = 0for i in range(1, 2 * M + 1):res = max(res, s[n] - s[start] - maxNum(start + i, max(i, M)))return resreturn maxNum(0, 1)

更优雅的写法

    def stoneGameII(self, A: List[int]) -> int:N = len(A)for i in range(N - 2, -1, -1):A[i] += A[i + 1]from functools import lru_cache@lru_cache(None)def dp(i, m):if i + 2 * m >= N: return A[i]return A[i] - min(dp(i + x, max(m, x)) for x in range(1, 2 * m + 1))return dp(0, 1)