LeetCode 1563. 石子游戏 V

Categories:

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

题目描述

✅ 1563. 石子游戏 V

思路分析

解法一：区间动态规划（推荐）

核心思路：

定义 dp[i][j] 为 Alice 在区间 [i, j] 内能获得的最大分数

枚举分割点 k（将区间分为 [i, k] 和 [k+1, j] 两部分），根据两侧总和决定 Alice 选哪侧

用前缀和 preSum 快速计算区间和：若左侧和 < 右侧和，Alice 选左侧得 sum(i,k) + dp[i][k]；左 > 右则选右侧；相等时取两者中的较大值

区间 DP 按区间长度从小到大递推

复杂度分析：

时间复杂度：O(n²)，其中 n 为数组长度，枚举所有区间及分割点

空间复杂度：O(n²)，dp 数组空间

class Solution {
    public int stoneGameV(int[] stoneValue) {
        int n = stoneValue.length;
        int[] preSum = new int[n + 1];

        for (int i = 0; i < n; i++) {
            preSum[i + 1] = preSum[i] + stoneValue[i];
        }

        int[][] dp = new int[n][n];

        // 区间长度从 2 开始枚举
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;

                for (int k = i; k < j; k++) {
                    int leftSum = preSum[k + 1] - preSum[i];
                    int rightSum = preSum[j + 1] - preSum[k + 1];

                    if (leftSum < rightSum) {
                        dp[i][j] = Math.max(dp[i][j], leftSum + dp[i][k]);
                    } else if (leftSum > rightSum) {
                        dp[i][j] = Math.max(dp[i][j], rightSum + dp[k + 1][j]);
                    } else {
                        dp[i][j] = Math.max(dp[i][j], Math.max(leftSum + dp[i][k], rightSum + dp[k + 1][j]));
                    }
                }
            }
        }

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

func stoneGameV(stoneValue []int) int {
    n := len(stoneValue)
    preSum := make([]int, n+1)

    for i := 0; i < n; i++ {
        preSum[i+1] = preSum[i] + stoneValue[i]
    }

    dp := make([][]int, n)
    for i := range dp {
        dp[i] = make([]int, n)
    }

    // 区间长度从 2 开始枚举
    for length := 2; length <= n; length++ {
        for i := 0; i <= n-length; i++ {
            j := i + length - 1

            for k := i; k < j; k++ {
                leftSum := preSum[k+1] - preSum[i]
                rightSum := preSum[j+1] - preSum[k+1]

                if leftSum < rightSum {
                    dp[i][j] = max(dp[i][j], leftSum+dp[i][k])
                } else if leftSum > rightSum {
                    dp[i][j] = max(dp[i][j], rightSum+dp[k+1][j])
                } else {
                    dp[i][j] = max(dp[i][j], max(leftSum+dp[i][k], rightSum+dp[k+1][j]))
                }
            }
        }
    }

    return dp[0][n-1]
}

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

相似题目

题目	难度	考察点
877. 石子游戏	中等	博弈 / 动态规划
1140. 石子游戏 II	中等	动态规划
1406. 石子游戏 III	困难	动态规划
1510. 石子游戏 IV	困难	动态规划
516. 最长回文子序列	中等	区间动态规划
312. 戳气球	困难	区间动态规划

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2021/23928739