状态压缩dp

class Solution {
public:
    bool memo_dfs(int maxChoosableInteger, int desiredTotal, vector<int>& memo, int state){
        // 之前已经遍历过了，直接返回之前的结果。记忆化搜索中很重要的剪枝步骤.
        if(memo[state] != 2){
            return memo[state];
        }
        
        // 遍历[1, maxchoose],选择当前步加入的数字.
        for(int i = 1; i <= maxChoosableInteger; i++){
            int add_state = 1 << (i - 1);
            
            // 当前元素已经加入之前的状态中了,不需要继续加入.
            if((add_state & state) != 0){
                continue;
            }
            
            // 此时如果加入当前元素已经满足取胜条件,则return true.
            // 即选的这个数i大于等于累计和desiredTotal
            if(desiredTotal - i <= 0){
                memo[state] = 1;
                return memo[state];
            }

            // 或者 下一手中无法满足取胜条件, 即返回0,此时依然当前手胜利.
            if(!memo_dfs(maxChoosableInteger, desiredTotal - i, memo, state | add_state)){
                memo[state] = 1;
                return memo[state];
            }
        }
        
        // 如果遍历所有状态之后依然没有一个状态可以取胜,返回false.
        memo[state] = 0;
        
        return memo[state];
    }
    
    bool canIWin(int maxChoosableInteger, int desiredTotal) {
        vector<int> dp(1 << maxChoosableInteger, 2);
        
        // 小剪枝,所有元素的和一半无法到达目标(求和公式),则返回false.
        if((1 + maxChoosableInteger) * maxChoosableInteger / 2 < desiredTotal){
            return false;
        }
        
        // 记忆化搜索, 状态压缩数组主要是充当记忆化数组。
        int res = memo_dfs(maxChoosableInteger, desiredTotal, dp, 0);
        
        if(res == 1){
            return true;
        }

        return false;
    }
};