Leetcode:石头游戏(我怎样才能对它进行不同的编码)

Question

问题陈述：

，爱丽丝和鲍勃玩了一堆石头的游戏。一排排排列成偶数的桩，每一桩有一个正整数的石块桩数。

游戏的目标是用最多的石头来结束比赛。所有桩上的石块总数都是奇数，因此没有联系。

爱丽丝和鲍勃轮流来，爱丽丝先开始。每一回合，一名玩家从开始或从排的末尾取下整堆石头。这种情况一直持续到没有剩下的堆积如山的时候，在这一点上，拥有最多石头的人就会获胜。

假设Alice和Bob玩得最好，如果Alice赢了游戏，返回true，如果Bob赢了，返回false。

以下是我的实现：

def stoneGame(self, piles: List[int]) -> bool:
        # return the the score difference between alice and bob(alice - bob)
        def dfs(turn, i, j):
            if i > j: #no more stone left
                return 0
            
            if turn == "alice": #alice tries to maximize her score
                choice1 = piles[i] + dfs("bob", i+1, j)
                choice2 = piles[j] + dfs("bob", i, j-1)
                return max(choice1, choice2)
            
            if turn == "bob": #bob tries to minimize alice's score, bob's score is negative because I want to subtract it from alice
                choice1 = -piles[i] + dfs("alice", i+1, j)
                choice2 = -piles[j] + dfs("alice", i, j-1)
                return min(choice1, choice2) #take the smallest and subtract it from alice. 
        
        
        return (dfs("alice", 0, len(piles)-1)) > 0
        #if alice - bob > 0, that means alice has more points so she wins

我通过计算爱丽丝和鲍勃之间的网络差异来解决这个问题。我如何改变我的代码，使我能够记录爱丽丝和鲍勃的分数，而不只是跟踪他们的差异。

Answer 1

有一个O(1)解决方案: Alice总是赢。

假设桩数从1到n为n个偶数。

然后，偶数桩或奇数桩共同拥有更多的石头。

哪个奇偶有更多的石头是爱丽丝总是选择的，而鲍勃被迫选择另一个奇偶。

现在，当Alice需要做O(n)工作来执行这个策略时，她知道她有一个获胜的策略，所以赢不需要任何工作。