状压+博弈dp

LeetCode:我能赢吗

传送门:https://leetcode-cn.com/problems/can-i-win/

题目大意:

游戏的双方能在 1 ~ n 之间选择一个数加到Sum上，每个数只能选择一次。谁先将Sum 变得 >= Max , 谁就赢了。现在问你，给定 n , Sum.先手是否能赢(两方采取最优策略)。 (n <= 20 , Max <= 300).

思路：

很容易发现n 很小，可以直接状态压缩。但是有一个问题。直观的想法是开二维数组，这样时间复杂度依旧过不去。

发现一个很重要的性质:令状态S为当前已经选走的数的集合，当选走的集合被确定了，那么当前的Sum也被唯一确定了。所以只需要一维就能表征两个属性.

dp[i]的含义为: 当已经选走的数的集合为i时，我先手是否能赢。然后决策个数就是二进制中0的个数。

如此一来，采用记忆化搜索，dfs存两维，而dp只需要记录一维即可。递归出口即为 当 now >= Max.