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

有个问题想问下~
”如果x有n个子节点，比如有3个子节点，g值分别为{0,1,3}，那么g(x)的值是这个列表中第一个没有出现的>=0的值，此时g(x) = 2。“

看推理，只要知道g(x)=0 or 1即可，好像2，3，4等非1的正整数并没有什么用？那么“ 第一个没有出现的>=0的值”有什么特殊的意义吗？

leyhzm 发表于 2016-9-11 10:12
有个问题想问下~
”如果x有n个子节点，比如有3个子节点，g值分别为{0,1,3}，那么g(x)的值是这个列表中第一 ...

确实，表示“是否先手必赢”，我们只需要知道g的值是0还是非0就可以了。所以看起来好像g不需要取0和1之外的其他值。但是，别忘了g的更重要的性质是g(x, y) = g(x) ^ g(y)。如果g只能取0和1的话，这性质可就不一定成立了。

leetcode大神！过来膜一下

感谢分享！

好贴，先收藏了