LeetCode石子游戏：如何修改代码记录双方得分而非分差

Alice和Bob玩石子堆游戏：

• 有偶数堆石子排成一行，每堆石子数量为正整数 piles[i]
• 游戏目标是最终拥有最多石子，总石子数为奇数，不会出现平局
• Alice先手，两人轮流取行首或行尾的整堆石子，直到石子堆取完
• 假设两人都采取最优策略，返回Alice是否获胜（true）或Bob获胜（false）

def stoneGame(self, piles: List[int]) -> bool:
        # 返回 Alice 与 Bob 的得分差（Alice得分 - Bob得分）
        def dfs(turn, i, j):
            if i > j: # 没有剩余石子
                return 0
            
            if turn == "alice": # Alice 尝试最大化自己的得分
                choice1 = piles[i] + dfs("bob", i+1, j)
                choice2 = piles[j] + dfs("bob", i, j-1)
                return max(choice1, choice2)
            
            if turn == "bob": # Bob 尝试最小化 Alice 的得分，用负分表示 Bob 的得分以实现差值计算
                choice1 = -piles[i] + dfs("alice", i+1, j)
                choice2 = -piles[j] + dfs("alice", i, j-1)
                return min(choice1, choice2) # 取最小差值，等价于最大化 Bob 的得分
        
        return (dfs("alice", 0, len(piles)-1)) > 0
        # 若差值大于0，说明 Alice 得分更高，返回获胜

我当前通过计算Alice与Bob的得分差来解决问题，请问如何修改代码，使其能够分别记录Alice和Bob的得分，而非仅追踪分差？

要实现分别记录Alice和Bob的得分，只需调整DFS函数的返回值，让它返回包含双方最终得分的元组，而非单一的得分差值。每一轮递归中，根据当前玩家的最优策略，分别累加对应玩家的得分即可：

修改后的代码 #

from typing import List

def stoneGame(self, piles: List[int]) -> bool:
    # 返回当前区间[i,j]内，双方采取最优策略后的(Alice得分, Bob得分)
    def dfs(turn, i, j):
        if i > j:
            return (0, 0)
        
        if turn == "alice":
            # 取左边堆：Alice获得当前堆石子，剩余区间由Bob行动
            a1, b1 = dfs("bob", i+1, j)
            option_left = (piles[i] + a1, b1)
            
            # 取右边堆：Alice获得当前堆石子，剩余区间由Bob行动
            a2, b2 = dfs("bob", i, j-1)
            option_right = (piles[j] + a2, b2)
            
            # Alice选自己得分更高的选项
            return option_left if option_left[0] > option_right[0] else option_right
        
        else: # Bob的回合
            # 取左边堆：Bob获得当前堆石子，剩余区间由Alice行动
            a1, b1 = dfs("alice", i+1, j)
            option_left = (a1, piles[i] + b1)
            
            # 取右边堆：Bob获得当前堆石子，剩余区间由Alice行动
            a2, b2 = dfs("alice", i, j-1)
            option_right = (a2, piles[j] + b2)
            
            # Bob选自己得分更高的选项
            return option_left if option_left[1] > option_right[1] else option_right
    
    alice_total, bob_total = dfs("alice", 0, len(piles)-1)
    return alice_total > bob_total

代码说明 #

1. 返回值调整：DFS函数不再返回得分差，而是直接返回(Alice得分, Bob得分)的元组，清晰记录双方最终得分
2. 回合逻辑：
   • Alice回合：计算取左/右堆后的得分组合，选择能让自己总得分最高的选项
   • Bob回合：计算取左/右堆后的得分组合，选择能让自己总得分最高的选项（完全符合最优策略的设定）
3. 结果判断：最终调用DFS后，直接比较Alice和Bob的总得分，返回Alice是否获胜

可选优化：加入记忆化缓存 #

如果石子堆数量较多，递归会出现大量重复计算，可以用lru_cache缓存DFS结果提升效率：

from functools import lru_cache
from typing import List

def stoneGame(self, piles: List[int]) -> bool:
    @lru_cache(maxsize=None)
    def dfs(turn, i, j):
        if i > j:
            return (0, 0)
        
        if turn == "alice":
            a1, b1 = dfs("bob", i+1, j)
            option_left = (piles[i] + a1, b1)
            
            a2, b2 = dfs("bob", i, j-1)
            option_right = (piles[j] + a2, b2)
            
            return option_left if option_left[0] > option_right[0] else option_right
        
        else:
            a1, b1 = dfs("alice", i+1, j)
            option_left = (a1, piles[i] + b1)
            
            a2, b2 = dfs("alice", i, j-1)
            option_right = (a2, piles[j] + b2)
            
            return option_left if option_left[1] > option_right[1] else option_right
    
    alice_total, bob_total = dfs("alice", 0, len(piles)-1)
    dfs.cache_clear()  # 清除缓存避免内存泄漏
    return alice_total > bob_total

内容的提问来源于stack exchange，提问作者Michael Xia