algo-aha

博弈题用自顶向下带memo的递归写法，比自底向上的dp写法更清晰

能赢吗

• https://leetcode.com/problems/can-i-win/

bool canIWin(int maxInt, int desired) {
    if (maxInt >= desired) return true;
    if (maxInt * (maxInt + 1) / 2 < desired) return false;
    // 因为1<=maxInt<=20，memo需要1<<20大小
    // memo[i]：0 未计算、1 win、-1 lose
    vector<int> memo(1 << 20);
    // 把哪些数用过编码到maskUsed
    function<bool(int,int)> dp = [&](int desired, unsigned maskUsed) {
        if (desired <= 0) return false; // 对方已拿到desired
        if (memo[maskUsed] != 0) return memo[maskUsed] == 1;
        
        for (int i = 1; i <= maxInt; i++) {
            unsigned maskCur = 1 << (i - 1);
            if ((maskUsed & maskCur) == 0) { // 当前数还未用过
                if (!dp(desired - i, maskUsed | maskCur)) {
                    memo[maskUsed] = 1;
                    return true;
                }
            }
        }
        memo[maskUsed] = -1;
        return false;
    };
    return dp(desired, 0);
} 

猜数字游戏，需要多少钱才能保证赢

• https://leetcode.com/problems/guess-number-higher-or-lower-ii/

int getMoneyAmount(int n) {
    // 设dp[i][j]表示猜[i..j]数字的子问题保证赢需要多少钱，1<=i<=j<=n
    // dp[i][j] = min{ k + max(dp[i][k-1], dp[k+1][j]) }，i<=k<=j
    // 其中k+max(dp[i][k-1],dp[k+1][j])表示猜k保证赢需要多少钱，
    // dp[i][j] = min{...}表示所有保证赢的情况里最少需要多少钱。
    // 初始dp[i][i]=0

    vector<vector<int>> memo(n + 1, vector<int>(n + 1, INT_MAX));
    function<int(int,int)> dp = [&](int lo, int hi) {
        if (lo >= hi) return 0;
        if (memo[lo][hi] != INT_MAX) return memo[lo][hi];
        for (int k = lo; k <= hi; k++) {
            int money = k + max(dp(lo, k - 1), dp(k + 1, hi));
            memo[lo][hi] = min(memo[lo][hi], money);
        }
        return memo[lo][hi];
    };
    return dp(1, n);
}

只能从数组首尾取数，取得数的和较大的赢

• https://leetcode.com/problems/predict-the-winner/
• https://leetcode.com/problems/stone-game/

站在playe1的角度，自己得分越大越好、对手得分越小越好，这里让对手得分为负，minmax简化成max算法。

bool PredictTheWinner(vector<int>& nums) {
    // 设dp[i][j]表示当前玩家从nums[i..j]局面能得的最高分，0<=i<=j<N
    // dp[i][j] = max(nums[i]-dp[i+1][j], nums[j]-dp[i][j-1])
    // 初始dp[i][i]=nums[i]
    // 省掉i这维，用临时变量ndp，i从右往左遍历，j从左往右遍历
    // ndp[j] = max(nums[i]-dp[j], nums[j]-ndp[j-1])
    const int N = nums.size();
    vector<int> dp(N);
    for (int i = N - 1; i >= 0; i--) {
        vector<int> ndp(N);
        ndp[i] = nums[i];
        for (int j = i + 1; j < N; j++) {
            ndp[j] = max(nums[i] - dp[j], nums[j] - ndp[j-1]);
        }
        swap(dp, ndp);
    }
    return dp[N-1] >= 0;
}