LeetCode 877. 石子游戏

Categories:

题目描述
思路分析
1. 解法一：区间 DP（推荐）
相似题目

题目描述

✅ 877. 石子游戏

思路分析

解法一：区间 DP（推荐）

核心思路：

dp[i][j] 表示在区间 [i, j] 内先手相对后手的最大分差。

转移：dp[i][j] = max(piles[i] - dp[i+1][j], piles[j] - dp[i][j-1])。

若最终分差 > 0，则先手获胜。

复杂度分析：

时间复杂度：O(n^2)，其中 n 表示石子堆数量。

空间复杂度：O(n^2)，DP 表占用空间。

class Solution {
    public boolean stoneGame(int[] piles) {
        int n = piles.length;
        int[][] dp = new int[n][n];

        for (int i = 0; i < n; i++) {
            dp[i][i] = piles[i];
        }

        for (int len = 2; len <= n; len++) {
            for (int i = 0; i + len - 1 < n; i++) {
                int j = i + len - 1;
                dp[i][j] = Math.max(piles[i] - dp[i + 1][j], piles[j] - dp[i][j - 1]);
            }
        }

        return dp[0][n - 1] > 0;
    }
}

func stoneGame(piles []int) bool {
	n := len(piles)
	dp := make([][]int, n)
	for i := range dp {
		dp[i] = make([]int, n)
		dp[i][i] = piles[i]
	}

	for length := 2; length <= n; length++ {
		for i := 0; i+length-1 < n; i++ {
			j := i + length - 1
			left := piles[i] - dp[i+1][j]
			right := piles[j] - dp[i][j-1]
			if left > right {
				dp[i][j] = left
			} else {
				dp[i][j] = right
			}
		}
	}

	return dp[0][n-1] > 0
}

相似题目

题目	难度	考察点
486. 预测赢家	中等	区间 DP
877. 石子游戏	中等	区间 DP
1140. 石子游戏 II	中等	博弈 DP
1406. 石子游戏 III	困难	博弈 DP
1510. 石子游戏 IV	困难	博弈 DP

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/97667882