leetcode1140.石子游戏II

Posted on | In |
Words count in article: 604 | Reading time ≈ 2

爱丽丝和鲍勃继续他们的石子游戏。许多堆石子 排成一行，每堆都有正整数颗石子 piles[i]。游戏以谁手中的石子最多来决出胜负。

爱丽丝和鲍勃轮流进行，爱丽丝先开始。最初，M = 1。

在每个玩家的回合中，该玩家可以拿走剩下的 前 X 堆的所有石子，其中 1 <= X <= 2M。然后，令 M = max(M, X)。

游戏一直持续到所有石子都被拿走。

假设爱丽丝和鲍勃都发挥出最佳水平，返回爱丽丝可以得到的最大数量的石头。

示例：

1
2
3
输入：piles = [2,7,9,4,4]
输出：10
解释：如果一开始Alice取了一堆，Bob取了两堆，然后Alice再取两堆。爱丽丝可以得到2 + 4 + 4 = 10堆。如果Alice一开始拿走了两堆，那么Bob可以拿走剩下的三堆。在这种情况下，Alice得到2 + 7 = 9堆。返回10，因为它更大。

分析：

1
2
3
4
5
6
状态表示：
	f[i, j]表示当石子为i~n，M=j时Alice可以得到的最大数量
状态转移：
	f[i][j] = max(f[i][j], s[n] - s[i - 1] - f[i + k][max(k, j)])
	f[i + k][max(k, j)] 表示Bob可以获得的石子， s[n] - s[i - 1] - f[i + k][max(k, j)]表示Alice可以获得的石子
	s[n] - s[i - 1]前缀和优化，表示i~n的石子数量

代码

  • C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int stoneGameII(vector<int>& piles) {
        int n = piles.size();
        vector<vector<int>> f(n + 2, vector<int>(n + 1, 0));
        vector<int> s(n + 1);

        for (int i = 1;i <= n;i ++)
            s[i] = s[i - 1] + piles[i - 1];

        for (int i = n;i;i --)
            for (int j = 1;j <= n;j ++)
                for (int k = 1;i + k - 1 <= n && k <= 2 * j;k ++)
                    f[i][j] = max(f[i][j], s[n] - s[i - 1] - f[i + k][max(k, j)]);

        return f[1][1];
    }
};

  • Golang

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
26
27
func Max(x, y int) int {
    if x > y {
        return x
    }

    return y
}

func stoneGameII(piles []int) int {
    var n int = len(piles)
    var f  [105][105]int
    var s [105]int

    for i := 1;i <= n;i += 1 {
        s[i] = piles[i - 1] + s[i - 1]
    }

    for i := n;i > 0;i -- {
        for j := 1;j <= n;j ++ {
            for k := 1;i + k - 1 <= n && k <= 2 * j;k ++ {
                f[i][j] = Max(f[i][j], s[n] - s[i - 1] - f[i + k][Max(k, j)]);
            }
        }
    }

    return f[1][1];
}

[原题链接](1140. 石子游戏 II - 力扣（Leetcode）)

0%