LeetCode 1140. 石子游戏 II（DP）*

示例：
输入：piles = [2,7,9,4,4]
输出：10
解释：
如果亚历克斯在开始时拿走一堆石子，李拿走两堆，接着亚历克斯也拿走两堆。
在这种情况下，亚历克斯可以拿到 2 + 4 + 4 = 10 颗石子。 

如果亚历克斯在开始时拿走两堆石子，那么李就可以拿走剩下全部三堆石子。
在这种情况下，亚历克斯可以拿到 2 + 7 = 9 颗石子。
所以我们返回更大的 10。 
 
提示：
1 <= piles.length <= 100
1 <= piles[i] <= 10 ^ 4

class Solution {
public:
    int stoneGameII(vector<int>& piles) {
        int i, m, x, n = piles.size();
        vector<int> presum(piles.size()+1, 0);
        for(i = 1; i <= n; ++i)
            presum[i] = presum[i-1]+piles[i-1];
        if(piles.size() <= 2)
            return piles[n-1];
        vector<vector<int>> dp(n+1,vector<int>(n+1,0));
        //dp[i][m] 表示 剩余i堆石头，M为m时能得到的最多石头
        for(i = 0; i <= n; ++i)
        {
            for(m = i; m <= n; ++m)
            {	// m >= i。可以全部拿走
                dp[i][m] = presum[n]-presum[n-i];//可以全部拿走
            }
        }
        for(i = 1; i <= n; ++i)
        {
            for(m = 1; m <= n; ++m)
            {
                for(x = 1; x <= min(2*m, i); ++x)
                {
                    dp[i][m] = max(dp[i][m], presum[n]-presum[n-i]-dp[i-x][min(n,max(x, m))]);
                    // 倒着遍历，剩余1个，剩余2个。。。
                    // 剩余 i 堆
                    // presum[n]-presum[n-i] 表示剩余的石子总数
                    // 我假设拿了 前 x 堆，
                    // 那么对手,从剩余的 i-x 堆中，取最多能取的
                    // dp[i-x][min(n,max(x, m))] 个, 总的数量减去对手拿的
                }
            }
        }
        return dp[n][1];
    }
};