石子游戏 V

题目描述

给定一个整数数组 stones，其中 stones[i] 表示第 i 堆石子的数量。Alice 和 Bob 轮流进行自己的回合，由 Alice 开始。

每一回合，玩家需要从石堆的任意一端（最左边或最右边）移走一堆石子。玩家的得分是所移走石堆中的石子数量。当所有石堆都被移走后，得分更高的玩家获胜。

假设 Alice 和 Bob 都采用最优策略，如果 Alice 能赢，返回 true；否则返回 false。

解题过程

这是一个典型的区间动态规划问题，涉及到两个玩家在序列两端进行最优选择。

1. 问题分析

• 游戏在石子数组 stones 上进行
• 每次只能从最左或最右端取石子
• 玩家得分是所取石堆的石子数
• 双方都采取最优策略
• 判断先手（Alice）是否能获胜

2. 状态定义

定义 dp[i][j] 表示当石子堆为 stones[i...j] 时，先手玩家能比后手玩家多得的最大分数。

• 如果 dp[0][n-1] > 0，则 Alice 获胜
• 如果 dp[0][n-1] = 0，则平局
• 如果 dp[0][n-1] < 0，则 Alice 失败

3. 状态转移方程

对于区间 [i, j]，先手玩家有两种选择：

1. 取左端 stones[i]：

   • 先手获得 stones[i] 分
   • 剩下的区间是 [i+1, j]，此时后手变成先手
   • 后手在 [i+1, j] 区间能比先手多得 dp[i+1][j] 分
   • 所以先手实际能比后手多得：stones[i] - dp[i+1][j]

2. 取右端 stones[j]：

   • 先手获得 stones[j] 分
   • 剩下的区间是 [i, j-1]，此时后手变成先手
   • 后手在 [i, j-1] 区间能比先手多得 dp[i][j-1] 分
   • 所以先手实际能比后手多得：stones[j] - dp[i][j-1]

先手玩家会选择对自己更有利的方案：
dp[i][j] = max(stones[i] - dp[i+1][j], stones[j] - dp[i][j-1])

4. 边界条件

当区间长度为 1 时（即 i = j）：

• 只有一堆石子，先手直接取走
• dp[i][i] = stones[i]

5. 计算顺序

由于区间动态规划依赖于更小的区间，我们需要：

• 按区间长度从小到大计算
• 先计算所有长度为 1 的区间
• 然后计算长度为 2、3、...、n 的区间

6. 算法实现

def stoneGame(stones):
    n = len(stones)
    if n == 0:
        return False
    
    # 创建 dp 数组
    dp = [[0] * n for _ in range(n)]
    
    # 初始化：长度为 1 的区间
    for i in range(n):
        dp[i][i] = stones[i]
    
    # 按区间长度从小到大计算
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            # 状态转移
            left_choice = stones[i] - dp[i+1][j]
            right_choice = stones[j] - dp[i][j-1]
            dp[i][j] = max(left_choice, right_choice)
    
    # 判断 Alice 是否能赢
    return dp[0][n-1] > 0

7. 示例分析

以 stones = [5, 3, 4, 5] 为例：

初始化（长度为 1 的区间）：

dp[0][0] = 5
dp[1][1] = 3  
dp[2][2] = 4
dp[3][3] = 5

长度为 2 的区间：

• [0,1]: max(5-dp[1][1], 3-dp[0][0]) = max(5-3, 3-5) = max(2, -2) = 2
• [1,2]: max(3-4, 4-3) = max(-1, 1) = 1
• [2,3]: max(4-5, 5-4) = max(-1, 1) = 1

长度为 3 的区间：

• [0,2]: max(5-dp[1][2], 4-dp[0][1]) = max(5-1, 4-2) = max(4, 2) = 4
• [1,3]: max(3-dp[2][3], 5-dp[1][2]) = max(3-1, 5-1) = max(2, 4) = 4

长度为 4 的区间：

• [0,3]: max(5-dp[1][3], 5-dp[0][2]) = max(5-4, 5-4) = max(1, 1) = 1

最终 dp[0][3] = 1 > 0，所以 Alice 获胜。

8. 复杂度分析

• 时间复杂度：O(n²)，需要填充 n²/2 个状态
• 空间复杂度：O(n²)，用于存储 dp 数组

这个解法清晰地展示了区间动态规划在博弈问题中的应用，通过分析双方的最优策略来解决问题。