石子游戏Ⅴ:区间dp

题目

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

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

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

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

链接

1563. 石子游戏 V

代码

class Solution {
    private int n;
    private int[] prefix;   // 前缀和数组
    private int[] nums;     // 原数组
    private Integer[][] memo; // 记忆化数组

    public int stoneGameV(int[] stoneValue) {
        n = stoneValue.length;
        nums = stoneValue;

        // 构建前缀和：prefix[i] = sum(stoneValue[0..i-1])
        prefix = new int[n + 1];
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }

        memo = new Integer[n][n];
        return dfs(0, n - 1);
    }

    // 返回在区间 [i, j] 上 Alice 能获得的最大分数
    private int dfs(int i, int j) {
        if (i >= j) {
            return 0; // 只剩一块石子，无法分割
        }
        if (memo[i][j] != null) {
            return memo[i][j];
        }

        int ans = 0;
        int leftSum = 0;
        int rightSum = prefix[j + 1] - prefix[i]; // [i..j] 的总和

        // 枚举所有分割点 k：[i..k] 和 [k+1..j]
        for (int k = i; k < j; k++) {
            leftSum += nums[k];
            rightSum -= nums[k];

            if (leftSum < rightSum) {
                // Bob 丢弃右段，Alice 保留左段，继续在 [i, k] 玩
                // 剪枝：若当前最优解已优于 2*leftSum，跳过
                if (ans > leftSum * 2) {
                    continue;
                }
                ans = Math.max(ans, leftSum + dfs(i, k));
            } else if (leftSum > rightSum) {
                // Bob 丢弃左段，Alice 保留右段，继续在 [k+1, j] 玩
                // 剪枝：若当前最优解已优于 2*rightSum，后续 k 只会让 rightSum 更小，直接 break
                if (ans > rightSum * 2) {
                    break;
                }
                ans = Math.max(ans, rightSum + dfs(k + 1, j));
            } else {
                // 两段相等，Alice 可以任选一段保留
                ans = Math.max(ans, Math.max(
                        leftSum + dfs(i, k),
                        rightSum + dfs(k + 1, j)
                ));
            }
        }

        memo[i][j] = ans;
        return ans;
    }
}

‍