leetcode464：动态规划

在 "100 game" 这个游戏中，两名玩家轮流选择从 1 到 10 的任意整数，累计整数和，先使得累计整数和达到 100 的玩家，即为胜者。

如果我们将游戏规则改为 “玩家不能重复使用整数” 呢？

例如，两个玩家可以轮流从公共整数池中抽取从 1 到 15 的整数（不放回），直到累计整数和 >= 100。

给定一个整数 maxChoosableInteger （整数池中可选择的最大数）和另一个整数 desiredTotal（累计和），判断先出手的玩家是否能稳赢（假设两位玩家游戏时都表现最佳）？

你可以假设 maxChoosableInteger 不会大于 20， desiredTotal 不会大于 300。

示例：

输入：
       maxChoosableInteger = 10
         desiredTotal = 11
输出：
     false

解释：
无论第一个玩家选择哪个整数，他都会失败。
第一个玩家可以选择从 1 到 10 的整数。
如果第一个玩家选择 1，那么第二个玩家只能选择从 2 到 10 的整数。
第二个玩家可以通过选择整数 10（那么累积和为 11 >= desiredTotal），从而取得胜利.
同样地，第一个玩家选择任意其他整数，第二个玩家都会赢。

思路

• 忆化dfs。一开始考虑到A先选，只要有一个选择的数返回true就行，B选择时，需要B之后A的每一次返回true，B才能返回true。这里，B选择时返回true的含义和A选择时的true含义是一样的，true代表A赢。

class Solution {
    public boolean canIWin(int nums, int sum) {
        if(sum==0) return true;
        if((1+nums)*nums/2<sum) return false;
        return dfs(nums,sum,0,new int[1<<20],true);
    }
    boolean dfs(int nums,int sum,int visited,int[] memo,boolean turn){
        if(memo[visited]==1) return true;
        if(memo[visited]==2) return false;
        if(sum<=0){
            if(turn){
                memo[visited]=2;
                return false;
            }
            memo[visited]=1;
            return true;
        }
        for(int i=nums;i>0;i--){
            if(((visited>>(i-1))&1)==1) continue;
            if(turn&&dfs(nums,sum-i,visited|(1<<(i-1)),memo,turn==true?false:true)){//A 一种情况就够了
                memo[visited]=1;
                return true;
            }
            else if(!turn&&!dfs(nums,sum-i,visited|(1<<(i-1)),memo,turn==true?false:true)){ //B 的每种情况都需要要A赢
                memo[visited]=2;  
                return false;
            }
        }
        if(turn){//A true ,B false
            memo[visited]=2;
        }else{
            memo[visited]=1;
        }
        return !turn;
    }