Google的“+-游戏”最优策略下的O(N^2) DP解法

这这！蛮有趣的样子～

膜拜，楼主太神啦。
从状态(2, 3, 4)开始，我们能进入的可能状态是  // 挑出其中一个数减去2，如果结果小于2，删除
(2-2, 3, 4) => (3,4)
(2, 3-1, 4) => (2,4)
(2, 3, 4-2) => (2,2,3)
(2, 3, 2, 2) => (2,2,2,3)
为什么 (2, 3, 2, 2) => (2,2,2,3) 这个可以，不是至少要flip不？why 可以一把4 拆成两个2呢？
(2, 3-1, 4) => (2,4) 这个楼主是不是笔误，应该为 (2, 3-2, 4) => (2,4) 呢？
还是我的理解有误？

lchen77 发表于 2015-8-27 09:57
膜拜，楼主太神啦。
从状态(2, 3, 4)开始，我们能进入的可能状态是  // 挑出其中一个数减去2，如果结果小 ...

这些都是笔误，多谢指出。3-1应该是3-2，至于那个2,3,2,2，其实应该是2,3,1,1 => 2,3

感谢楼主，这类型的题还是见得少了

楼主的推导只用了一个dp函数，有个很明显的问题。

例如++++--++的情况。4, 2 的case 按楼主的推导，应该是先手负的。但实际上可以先手胜，通过在 4 的部分强迫自己负的情况下。

我觉得至少要两个dp函数，winable和losable，然后推导一个表出来。winable[4]和losable[4]都是true，这就是这题妙处所在。

不好意思，说错了。

看了下nim游戏，明白楼主的意思了。楼主并没有给出sg函数在这题的具体形式，但是这个函数是存在的。

赞一个先

不知道楼主能否详细解释一下定理一呢？
在给定定理一的条件下来看定理二以及后面的DP设计都挺make sense的

求定理1，2的解释。多谢

考这题是纯黑了吧

看的合不拢腿了