石子游戏 II

爱丽丝和鲍勃继续他们的石子游戏。许多堆石子 排成一行，每堆都有正整数颗石子 piles[i]。游戏以谁手中的石子最多来决出胜负。
爱丽丝和鲍勃轮流进行，爱丽丝先开始。最初，M = 1。
在每个玩家的回合中，该玩家可以拿走剩下的 前 X 堆的所有石子，其中 1 <= X <= 2M。然后，令 M = max(M, X)。
游戏一直持续到所有石子都被拿走。
假设爱丽丝和鲍勃都发挥出最佳水平，返回爱丽丝可以得到的最大数量的石头。

  • 输入：piles = [2,7,9,4,4]

  • 输出：10

  • 解释：如果一开始 Alice 取了一堆，Bob 取了两堆，然后 Alice 再取两堆。爱丽丝可以得到 2 + 4 + 4 = 10 堆。如果 Alice 一开始拿走了两堆，那么 Bob 可以拿走剩下的三堆。在这种情况下，Alice 得到 2 + 7 = 9 堆。返回 10，因为它更大。

  • 输入：piles = [1,2,3,4,5,100]

  • 输出：104

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
var stoneGameII = function(piles) {
    const sum=new Array(piles.length).fill(piles.at(-1));
    for(let i=piles.length-2;i>=0;i--){
        sum[i]=sum[i+1]+piles[i];
    }
    const cache=new Map();
    const dfs=(i,m)=>{
        if(cache.has(`${i}#${m}`)){
            return cache.get(`${i}#${m}`);
        }
        if(i>=piles.length) return 0;
        let t=Infinity;
        for(let x=1;x<=2*m;++x){
            t=Math.min(t,dfs(i+x,Math.max(m,x)));
        }
        cache.set(`${i}#${m}`,sum[i]-t);
        return sum[i]-t;
    }
    return dfs(0,1);
};