石子游戏VJava

文章发布较早，内容可能过时，阅读注意甄别。

# 题目

几块石子排成一行，每块石子都有一个关联值，关联值为整数，由数组 stoneValue 给出。

游戏中的每一轮：Alice 会将这行石子分成两个非空行（即，左侧行和右侧行）；Bob 负责计算每一行的值，即此行中所有石子的值的总和。Bob 会丢弃值最大的行，Alice 的得分为剩下那行的值（每轮累加）。如果两行的值相等，Bob 让 Alice 决定丢弃哪一行。下一轮从剩下的那一行开始。

只剩下一块石子时，游戏结束。Alice 的分数最初为 0 。

返回 Alice 能够获得的最大分数。

示例 1：

输入：stoneValue = [6,2,3,4,5,5]
输出：18
解释：在第一轮中，Alice 将行划分为 [6，2，3]，[4，5，5] 。左行的值是 11 ，右行的值是 14 。Bob 丢弃了右行，Alice 的分数现在是 11 。
在第二轮中，Alice 将行分成 [6]，[2，3] 。这一次 Bob 扔掉了左行，Alice 的分数变成了 16（11 + 5）。
最后一轮 Alice 只能将行分成 [2]，[3] 。Bob 扔掉右行，Alice 的分数现在是 18（16 + 2）。游戏结束，因为这行只剩下一块石头了。

示例 2：

输入：stoneValue = [7,7,7,7,7,7,7]
输出：28

示例 3：

输入：stoneValue = [4]
输出：0

提示：

1 <= stoneValue.length <= 500
1 <= stoneValue[i] <= 10^6

# 思路

# 解法

class Solution {
    public int stoneGameV(int[] stoneValue) {
        // 从上一轮 [l:r] 进入本轮的 [i:j]，要么扔掉 [l:i-1]，剩下 [i:r]，要么扔掉 [j+1:r]，剩下 [l:j]
        // 且扔掉的条件需满足 sum[l:i-1] >= sum[i:j] 或 sum[j+1:r] >= sum[i:j]
        // 要求 [i:j] 能获得的最大分数，可以从左到右分割 [i:j]，计算 [i:k] 以及 [k+1:j] 的分数，

        int n = stoneValue.length;
        if (n == 1) return 0;
        // 计算区间和，先用前缀和预处理
        int[] sum = new int[n+1];
        for (int i = 1; i <= n; i++) {
            sum[i] = sum[i-1] + stoneValue[i-1];
        }

        int[][] dp = new int[n][n];
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i + len - 1 < n; i++) {
                int j = i + len - 1;
                for (int k = i; k < j; k++) {
                    int left = sum[k+1] - sum[i], right = sum[j+1] - sum[k+1];
                    if (left < right) {
                        // 找左边最值
                        dp[i][j] = Math.max(dp[i][j], left + dp[i][k]);
                    } else if (left > right){
                        // 找右边
                        dp[i][j] = Math.max(dp[i][j], right + dp[k+1][j]);
                    } else {
                        // 左右都可以
                        dp[i][j] = Math.max(dp[i][j], Math.max(left + dp[i][k], right + dp[k+1][j]));
                    }
                }
            }
        }

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

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
28
29
30
31
32
33
34
35
36
37
38

# 总结

分析出几种情况，然后分别对各个情况实现

#Java