LeetCode1563：石子游戏V

题目

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

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

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

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

Solution

$dp[l][r]$ 表示区间 $[l,r]$ Alice能得到的最大值，然后区间dp。

若$sum[l…mid] == sum[mid+1…r]$ ，则 $dp[l][r] = max(dp[l][r], dp[l][mid] + dp[mid + 1][r] + sum[l…mid])$。

若$sum[l…mid] != sum[mid+1…r]$ :

• $sum[l…mid] > sum[mid + 1][r]$ ，则 $dp[l][r] = max(dp[l][r], dp[mid + 1][r] + sum[mid+1…r])$。
• $sum[l…mid] < sum[mid + 1][r]$ ，则 $dp[l][r] = max(dp[l][r], dp[l][mid] + sum[l…mid])$。

Code

class Solution {
    public int stoneGameV(int[] stoneValue) {
        int n = stoneValue.length;
        int[][] dp = new int[n][n];
        int[] sum = new int[n];
        sum[0] = stoneValue[0];
        for (int i = 1; i < n; i++) {
            sum[i] = sum[i - 1] + stoneValue[i];
        }
        for (int len = 2; len <= n; len++) {
            for (int l = 0; l + len - 1 < n; l++) {
                int r = l + len - 1;
                for (int mid = l; mid < r; mid++) {
                    int fl = sum[mid] - (l > 0 ? sum[l - 1] : 0);
                    int fr = sum[r] - sum[mid];
                    if (fl == fr) {
                        dp[l][r] = Math.max(dp[l][r], Math.max(dp[l][mid], dp[mid + 1][r]) + fl);
                    } else {
                        if (fl > fr) {
                            dp[l][r] = Math.max(dp[l][r], dp[mid + 1][r] + fr);
                        } else {
                            dp[l][r] = Math.max(dp[l][r], dp[l][mid] + fl);
                        }
                    }
                }
            }
        }
        return dp[0][n - 1];
    }
}