石子游戏 VII

/*
题目思路：
1. 使用动态规划来解决这个问题。
2. dp[i][j] 表示从 i 到 j 的石子数组中，当前玩家与另一个玩家得分差的最大值。
3. 如果当前玩家选择左边的石子，得分差为 stones[i] - dp[i+1][j]。
4. 如果当前玩家选择右边的石子，得分差为 stones[j] - dp[i][j-1]。
5. 转移方程为 dp[i][j] = max(stones[i] - dp[i+1][j], stones[j] - dp[i][j-1])。
6. 最终结果为 dp[0][n-1]。
*/
import java.util.stream.IntStream;
public int stoneGameVII(int[] stones) {
    int n = stones.length;
    int[][] dp = new int[n][n];
    int[] prefixSum = IntStream.range(0, n + 1).map(i -> i == 0 ? 0 : IntStream.range(0, i).map(j -> stones[j]).sum()).toArray();
    IntStream.range(1, n).forEach(length ->
        IntStream.range(0, n - length).forEach(i -> {
            int j = i + length;
            int sum = prefixSum[j + 1] - prefixSum[i];
            dp[i][j] = Math.max(sum - stones[i] - dp[i + 1][j], sum - stones[j] - dp[i][j - 1]);
        })
    );
    return dp[0][n - 1];
}