石子游戏 II

1140. 石子游戏 II

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

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

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

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

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

示例 1：

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

示例 2:

输入：piles = [1,2,3,4,5,100]
输出：104

提示：

1 <= piles.length <= 100
1 <= piles[i] <= 10⁴

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: int stoneGameII(vector<int>& piles) { } };

golang 解法, 执行用时: 0 ms, 内存消耗: 4.5 MB, 提交时间: 2023-02-22 09:24:06

func stoneGameII(piles []int) int {
    n := len(piles)
    f := make([][]int, n)
    for i := range f {
        f[i] = make([]int, n+1)
    }
    for i, s := n-1, 0; i >= 0; i-- {
        s += piles[i]
        for m := 1; m <= i/2+1; m++ {
            if i+m*2 >= n {
                f[i][m] = s
            } else {
                mn := math.MaxInt
                for x := 1; x <= m*2; x++ {
                    mn = min(mn, f[i+x][max(m, x)])
                }
                f[i][m] = s - mn
            }
        }
    }
    return f[0][1]
}

func min(a, b int) int { if b < a { return b }; return a }
func max(a, b int) int { if b > a { return b }; return a }

python3 解法, 执行用时: 100 ms, 内存消耗: 15.2 MB, 提交时间: 2023-02-22 09:23:50

class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        s, n = 0, len(piles)
        f = [[0] * (n + 1) for _ in range(n)]
        for i in range(n - 1, -1, -1):
            s += piles[i]
            for m in range(1, i // 2 + 2):
                if i + m * 2 >= n:
                    f[i][m] = s
                else:
                    f[i][m] = s - min(f[i + x][max(m, x)] for x in range(1, m * 2 + 1))
        return f[0][1]

java 解法, 执行用时: 2 ms, 内存消耗: 39.2 MB, 提交时间: 2023-02-22 09:23:20

class Solution {
    private int[][] cache;
    private int[] s;

    public int stoneGameII(int[] piles) {
        s = piles;
        int n = s.length;
        for (int i = n - 2; i >= 0; --i)
            s[i] += s[i + 1]; // 后缀和

        cache = new int[n - 1][(n + 1) / 4 + 1];
        for (int i = 0; i < n - 1; i++)
            Arrays.fill(cache[i], -1); // -1 表示没有访问过
        return dfs(0, 1);
    }

    private int dfs(int i, int m) {
        if (i + m * 2 >= s.length) return s[i];
        if (cache[i][m] != -1) return cache[i][m];
        int mn = Integer.MAX_VALUE;
        for (int x = 1; x <= m * 2; ++x)
            mn = Math.min(mn, dfs(i + x, Math.max(m, x)));
        return cache[i][m] = s[i] - mn;
    }
}

golang 解法, 执行用时: 4 ms, 内存消耗: 2.8 MB, 提交时间: 2023-02-22 09:22:53

func stoneGameII(s []int) int {
    n := len(s)
    for i := n - 2; i >= 0; i-- {
        s[i] += s[i+1] // 后缀和
    }

    cache := make([][]int, n-1)
    for i := range cache {
        cache[i] = make([]int, (n+1)/4+1)
        for j := range cache[i] {
            cache[i][j] = -1 // -1 表示没有访问过
        }
    }
    var dfs func(int, int) int
    dfs = func(i, m int) int {
        if i+m*2 >= n {
            return s[i]
        }
        v := &cache[i][m]
        if *v != -1 {
            return *v
        }
        mn := math.MaxInt
        for x := 1; x <= m*2; x++ {
            mn = min(mn, dfs(i+x, max(m, x)))
        }
        res := s[i] - mn
        *v = res
        return res
    }
    return dfs(0, 1)
}

func min(a, b int) int { if b < a { return b }; return a }
func max(a, b int) int { if b > a { return b }; return a }

python3 解法, 执行用时: 136 ms, 内存消耗: 16.8 MB, 提交时间: 2023-02-22 09:22:21

'''
记忆化搜索
'''
class Solution:
    def stoneGameII(self, s: List[int]) -> int:
        n = len(s)
        for i in range(n - 2, -1, -1):
            s[i] += s[i + 1]  # 后缀和

        @cache
        def dfs(i: int, m: int) -> int:
            if i + m * 2 >= n:  # 能全拿
                return s[i]
            return s[i] - min(dfs(i + x, max(m, x)) for x in range(1, m * 2 + 1))
        return dfs(0, 1)

golang 解法, 执行用时: 24 ms, 内存消耗: 5.5 MB, 提交时间: 2022-11-27 11:34:06

func stoneGameII(piles []int) int {
    n := len(piles)
    s := make([]int, n)
    s[n-1] = piles[n-1]
    for i := n-2; i >=0; i--{
        s[i] = s[i+1] + piles[i]
    } 
    memo := map[[2]int]int{}
    var dfs func(i int, M int) int
    dfs = func(i int, M int) int {
        tmp := [2]int{i, M}
        _, ok := memo[tmp]
        if (ok == true){
            return memo[tmp]
        }
        if i >= n{
            return 0
        }
        if i + 2*M >= n{
            return s[i]
        }
        max_tmp := 0
        for x:= 1; x < 2*M+1; x++{
            max_tmp = Max(max_tmp, s[i] - dfs(i+x, Max(M, x)))
        }
        memo[tmp] = max_tmp
        return max_tmp
    }
    return dfs(0, 1)
}


func Max(a, b int) int{
    if (a > b){
        return a
    }
    return b
}

golang 解法, 执行用时: 4 ms, 内存消耗: 4.8 MB, 提交时间: 2022-11-27 11:33:41

func stoneGameII(ns []int) int {
    n := len(ns)
    var memo = make([][]*int, n, n)
    for i := range memo {
        memo[i] = make([]*int, n, n)
    }
    sum := make([]int, n, n)
    sum[n - 1] = ns[n - 1]
    for i := n - 2; i >= 0; i-- {
        sum[i] += sum[i + 1] + ns[i]
    }
    return dfs(memo, 0, 1, n, sum)
}

func dfs(memo [][]*int, index int, M int, n int, sum []int) int {
    if index >= n {
        return 0
    }
    
    // 这里一定要先进行判断，防止出现获取memo的值的时候会越界
    if n - index <= 2 * M {
        return sum[index]
    }
    
    if memo[index][M] != nil {
        return *memo[index][M]
    }
    x := math.MaxInt
    for i := 1; i <= 2 * M; i++ {
        x = min(x, dfs(memo, index + i, max(M, i), n, sum))
    }
    res := sum[index] - x
    memo[index][M] = &res
    return res
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}

python3 解法, 执行用时: 212 ms, 内存消耗: 16.3 MB, 提交时间: 2022-11-27 11:32:18

class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        # 数据规模与记忆化
        n, memo = len(piles), dict()
        
        # s[i] 表示第 i 堆石子到最后一堆石子的总石子数
        s = [0] * (n + 1)
        for i in range(n - 1, -1, -1):
            s[i] = s[i + 1] + piles[i]
            
        # dfs(i, M) 表示从第 i 堆石子开始取，最多能取 M 堆石子所能得到的最优值
        def dfs(i, M):
            # 如果已经搜索过，直接返回
            if (i, M) in memo:
                return memo[(i, M)]
            # 溢出拿不到任何石子
            if i >= n:
                return 0
            # 如果剩余堆数小于等于 2M， 那么可以全拿走
            if i + M * 2 >= n:
                return s[i]
            # 枚举拿 x 堆的最优值
            best = 0
            for x in range(1, M * 2 + 1):
                # 剩余石子减去对方最优策略
                best = max(best, s[i] - dfs(i + x, max(x, M)))
            # 记忆化
            memo[(i, M)] = best
            return best
        
        return dfs(0, 1)

java 解法, 执行用时: 6 ms, 内存消耗: 41.1 MB, 提交时间: 2022-11-27 11:31:52

class Solution {
    /**
     * dp[i][j]表示剩余[i : len - 1]堆时，M = j的情况下，先取的人能获得的最多石子数
     * 1. i + 2M >= len, dp[i][M] = sum[i : len - 1], 剩下的堆数能够直接全部取走，那么最优的情况就是剩下的石子总和
     * 2. i + 2M < len, dp[i][M] = max(dp[i][M], sum[i : len - 1] - dp[i + x][max(M, x)]), 其中 1 <= x <= 2M
     * ，剩下的堆数不能全部取走，那么最优情况就是让下一个人取的更少。
     * 对于我所有的x取值，下一个人从x开始取起，M变为max(M, x)，
     * 所以下一个人能取dp[i + x][max(M, x)]，我最多能取sum[i : len - 1] - dp[i + x][max(M, x)]。
     */
    public int stoneGameII(int[] piles) {
        int len = piles.length, sum = 0;
        int[][] dp = new int[len][len + 1];
        for (int i = len - 1; i >= 0; i--) {
            sum += piles[i];
            for (int M = 1; M <= len; M++) {
                if (i + 2 * M >= len) {
                    dp[i][M] = sum;
                } else {
                    for (int x = 1; x <= 2 * M; x++) {
                        dp[i][M] = Math.max(dp[i][M], sum - dp[i + x][Math.max(M, x)]);
                    }
                }
            }
        }
        return dp[0][1];
    }
}

上一题

下一题

详情