Readme

1140.Stone-Game-II

本题是典型的决策问题。设计solve(i,M)表示当前玩家可以从第i堆石头开始取、所取的堆数的上下限是[1,2M]，那么截止游戏结束所能得到的最大收益。

假设当前玩家取X堆，那么对手在之后所能得到的最大收益就是solve(i+X, max(X,M))。这就说明，对于当前玩家而言，如果本回合取X堆，根据此消彼长的规则，意味着截止游戏时能得到的最大收益就是sufSum[i] - solve(i+X, max(X,M))。所以为了使solve(i,M)最大，我们必然会取能使sufSum[i] - solve(i+X, max(X,M))最大的X。

递归的边界条件就是当i==n的时候，玩家不能再取石头，返回零。最终的答案就是solve(0,1)。