1690.石子游戏VII

链接：1690.石子游戏VII
难度：Medium
标签：数组、数学、动态规划、博弈
简介：给你一个整数数组 stones ，其中 stones[i] 表示 从左边开始 的第 i 个石头的值，如果爱丽丝和鲍勃都 发挥出最佳水平 ，请返回他们 得分的差值 。

题解 1 - python

• 编辑时间：2024-02-03
• 执行用时：4980ms
• 内存消耗：349.04MB
• 编程语言：python
• 解法介绍：dfs。

class Solution:
    def stoneGameVII(self, stones: List[int]) -> int:
        n = len(stones)
        dp = [[0] * n for _ in range(n)]
        sums = [0]
        for stone in stones: sums.append(sums[-1] + stone)
        @cache
        def dfs(l: int, r: int, f: int) -> int:
            if l == r: return 0
            v1 = sums[r + 1] - sums[l + 1]
            v2 = sums[r] - sums[l]
            res1 = -dfs(l + 1, r, -f) 
            res2 = -dfs(l, r - 1, -f) 
            # print(f'l = {l}, r = {r}, f = {f}, v1 = {v1}, v2 = {v2} res1 = {res1}, res2 = {res2}, res = {f * max(res1 + v1, res2 + v2)}')
            return max(res1 + v1, res2 + v2)
        return dfs(0, n - 1, 1)