@SomeBottle 在 Leetcode每日一题 —— 1406. 石子游戏 III 中发帖
思路
游戏过程中二者都只能从最左边拿走 1, 2 或者 3 堆,设 stoneValues 有 n 堆,首次轮到 Alice 时:
可以取走 0,剩下 [1, n-1];
可以取走 0, 1,剩下 [2, n-1];
可以取走 0, 1, 2,剩下 [3, n-1]。
到某一轮,轮到某位玩家时只能变动 i 下标及其之后的石头堆时,则可能剩下 [i+1, n-1], [i+2, n-1] 或者 [i+3, n-1]。
可以看到每次操作后留下的都是一个后缀区间,因此这题适合从后往前倒着递推。
可以定义 dp[i] 为当前玩家相对另一个玩家最多能领先的分数(因为在 i 这里两个人都有可能),但可以确定的是 dp[0] 肯定对应于 Alice 领先 Bob 的最多分数(因为 Alice 先手)。
递推时,如果当前玩家取了 i,则 [i+1, n-1] 就留给后一个玩家取(对应 d...