heihei12305

亚历克斯和李继续他们的石子游戏。许多堆石子 排成一行，每堆都有正整数颗石子 piles[i]。游戏以谁手中的石子最多来决出胜负。


亚历克斯和李轮流进行，亚历克斯先开始。最初，M = 1。


在每个玩家的回合中，该玩家可以拿走剩下的 前 X 堆的所有石子，其中 1 <= X <= 2M。然后，令 M = max(M, X)。


游戏一直持续到所有石子都被拿走。


假设亚历克斯和李都发挥出最佳水平，返回亚历克斯可以得到的最大数量的石头。

输入：piles = [2,7,9,4,4]
输出：10
解释：
如果亚历克斯在开始时拿走一堆石子，李拿走两堆，接着亚历克斯也拿走两堆。在这种情况下，亚历克斯可以拿到 2 + 4 + 4 = 10 颗石子。 
如果亚历克斯在开始时拿走两堆石子，那么李就可以拿走剩下全部三堆石子。在这种情况下，亚历克斯可以拿到 2 + 7 = 9 颗石子。
所以我们返回更大的 10。 

本题中，涉及到了两者之间的博弈问题，同时均发挥最佳水平，这使得解题思路为从后往前求解，而且为了避免重复计算，需要利用对象给计算结果记录下来。

var stoneGameII = function(piles) {
    let len = piles.length;
		//利用对象存储已求得的结果，避免重复调用，js中的对象运用很方便，不像c++，一般数组存储
    let vec = {};
    
		//计算从第i堆石子到最后一堆石子的总石子数
    let sum = new Array(len);
    sum[len-1] = piles[len-1];
    for(let i = len-2;i>=0;i--){
        sum[i] = sum[i+1] + piles[i];
    }
    
    //记忆化递归
    dfs = function(i,m){
				//判断是否已经计算过
        if(vec.hasOwnProperty([i,m])){
            return vec[[i,m]];
        }
				
				//如果已经取完，直接返回0
        if(i > len){
            return 0;
        }
				
				//如果可以直接取完，则直接取完
        if(i + m * 2 >= len){
            return sum[i];
        }
        
				//递归求得此时的最大值
        let best = 0;
        for(let x = 1;x < m*2+1; x++){
						//此处运用了博弈思想，此时的最优策略是 剩余石子减去对手的最优策略
            best = Math.max(best,sum[i]-dfs(i+x,Math.max(x,m)));
        }
        
				//将计算结果保存
        vec[[i,m]] = best;
        return best;
    }
    return dfs(0,1);
};