題目
Alex and Lee play a game with piles of stones. There are an even number of piles arranged in a row, and each pile has a positive integer number of stones piles[i].

The objective of the game is to end with the most stones. The total number of stones is odd, so there are no ties.

Alex and Lee take turns, with Alex starting first. Each turn, a player takes the entire pile of stones from either the beginning or the end of the row. This continues until there are no more piles left, at which point the person with the most stones wins.

Assuming Alex and Lee play optimally, return True if and only if Alex wins the game.

答案

class Solution {

    public boolean stoneGame(int[] piles) {
        /*
            First try:
            Define f[i][j]: 是否先手必勝?
            Base case: 只剩下一個(gè)pile，那先手直接拿掉這個(gè)pile
            但是就算先手可以拿掉這個(gè)pile，也不證明他能贏萤晴，輸贏要看手上石子多寡

            What if we define f[i][j]: 先手最多可以拿多少顆石子?
                                       如果后手能拿k顆妻怎，先手就能拿sum[i...j] - k顆
                                       如此可以將f[0][n - 1]問題規(guī)模逐漸縮小震檩，直到變?yōu)閒[i][j], where i == j(base case)
                                       
            最后比較f[0][n - 1](先手最多可以拿多少石子) 和 Math.max(f[1][n-1],f[0][n-2]) (后手最多可以拿多少石子) 來得知Alex是否可以必勝
        */
        int n = piles.length;
        int[][] f = new int[n][n];
        int[] cumsum = new int[n];

        int prev = 0;
        for(int i = 0; i < n; i++) {
            // Calculate cumulative sum
            if(i > 0) prev = cumsum[i - 1];
            cumsum[i] = piles[i] + prev;
            Arrays.fill(f[i], -1);
        }
        recur(piles, f, cumsum, 0, n - 1);
        if(f[0][n - 1] >= Math.max(f[0][n - 2], f[1][n - 1])) return true;
        return false;
    }
    public int recur(int[] piles, int[][] f, int[] cumsum, int left, int right) {
        // Base case
        if(left == right) {
            f[left][right] = piles[left];
            return f[left][right];
        }

        if(f[left][right] != -1) return f[left][right];
        int ans = 0;

        int cumulative_sum1 = cumsum[right] - cumsum[left + 1] + piles[left + 1];
        int cumulative_sum2 = cumsum[right - 1] - cumsum[left] + piles[left];
        int ans1 = recur(piles, f, cumsum, left + 1, right);
        int ans2 = Math.max(recur(piles, f, cumsum, left, right - 1), ans);
        f[left][right] = Math.max((cumulative_sum1 - ans1) + piles[left], (cumulative_sum2 - ans2) + piles[right]);

        return f[left][right];
    }
}