1690. 石子游戏 VII

leetcode
2k words

https://leetcode.cn/problems/stone-game-vii/description/

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int stoneGameVII(vector<int>& stones) {
        int n = stones.size();
        vector<int> sum(n + 1);
        vector<vector<int>> memo(n, vector<int>(n, 0));
        for (int i = 0; i < n; i++) {
            sum[i + 1] = sum[i] + stones[i];
        }

        function<int(int, int)> dfs = [&](int i, int j) -> int {
            if (i >= j) {
                return 0;
            }
            if (memo[i][j] != 0) {
                return memo[i][j];
            }
            int res = max(sum[j + 1] - sum[i + 1] - dfs(i + 1, j), sum[j] - sum[i] - dfs(i, j - 1));
            memo[i][j] = res;
            return res;
        };
        return dfs(0, n - 1);
    }
};

解释

  1. 这段代码是用来解决一个动态规划问题，特别是在一种石子游戏（Stone Game VII）的背景下。在这个游戏中，玩家轮流从一行石子中移除最左边或最右边的石子，每次移除后，玩家的得分增加剩余石子的总和。目标是最大化最终得分的差值。下面是代码的详细解释：

    初始化变量和前缀和

    1
    2
    3
    4
    5
    6
    int n = stones.size();
    vector<int> sum(n + 1);
    vector<vector<int>> memo(n, vector<int>(n, 0));
    for (int i = 0; i < n; i++) {
        sum[i + 1] = sum[i] + stones[i];
    }
    • n 是石子的数量。
    • sum 是一个前缀和数组，sum[i] 存储了从第 0 个石子到第 i-1 个石子的总和。
    • memo 是一个二维数组，用于记忆化递归，以避免重复计算相同的子问题。memo[i][j] 存储了从第 i 个石子到第 j 个石子之间的最大得分差。

    定义递归函数

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    function<int(int, int)> dfs = [&](int i, int j) -> int {
        if (i >= j) {
            return 0;
        }
        if (memo[i][j] != 0) {
            return memo[i][j];
        }
        int res = max(sum[j + 1] - sum[i + 1] - dfs(i + 1, j), sum[j] - sum[i] - dfs(i, j - 1));
        memo[i][j] = res;
        return res;
    };
    • 这个递归函数 dfs 被用来计算在从第 i 个石子到第 j 个石子之间玩游戏时能够获得的最大得分差。
    • 如果 i >= j，意味着没有石子可以移除，返回 0。
    • 如果 memo[i][j] 已经被计算过，则直接返回结果。
    • 计算移除左边或右边石子后，剩余石子总和减去对手在剩余石子中能获得的最大得分差的最大值，并将结果存储在 memo[i][j] 中。

    开始递归

    1
    return dfs(0, n - 1);
    • 从整个石子数组的开始到结束进行递归调用，计算出最大得分差。

    总结

    这个解决方案利用了动态规划的思想，通过记忆化递归来避免重复计算，并使用前缀和来快速计算石子的总和。该策略确保了在石子游戏中寻找最优策略时的效率和准确性。

    关键步骤

1
int res = max(sum[j + 1] - sum[i + 1] - dfs(i + 1, j), sum[j] - sum[i] - dfs(i, j - 1));

这行代码是石子游戏VII问题解法中的核心，它负责计算当前玩家在面对从第 i 个石子到第 j 个石子的子数组时能够获得的最大分数差。具体地说，它使用了动态规划与递归的混合方法来实现这一计算。

  • sum[j + 1] - sum[i + 1] 和 sum[j] - sum[i] 都是用来计算当前玩家可以直接获得的分数。前者是当当前玩家选择移除最左边的石子时，剩余石子的总和；后者是当当前玩家选择移除最右边的石子时，剩余石子的总和。
  • - dfs(i + 1, j) 和 - dfs(i, j - 1) 分别对应于上述两种情况之后，对手可能获得的最大分数差。当前玩家需要从这两种选择中选择一个最优解，即让自己的分数最大化。这里的 “分数最大化” 实际上是指在当前步骤之后的所有可能步骤中，最大化自己的分数与对手分数之差。
  • max(..., ...) 函数比较了这两种选择的结果，选出了使当前玩家分数差最大化的选择。
Comments