LeetCode-1406 石子游戏 III

Table of Contents

LeetCode-1406 石子游戏 III #

Solution 1 #

$dp[i]$ 代表从 $i$ 开始取的先手最大分差, 递归.

代码如下:

class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        n = len(stoneValue)
        
        @cache
        def f(i):
            if i >= n:
                return 0
            res = -inf
            for j in range(1, 4):
                res = max(res, sum(stoneValue[i: i + j]) - f(i + j))
            return res

        return 'Alice' if f(0) > 0 else ('Tie' if f(0) == 0 else 'Bob')