有趣的minimax

minimax是博弈论中比较经典的搜索算法。它的目标是在所有最差的情况下找到最好的情况。比如下棋，考虑当前你能下的所有情况，求出每种情况下，你能够获得的最小收益，然后对于每种情况，求出所有最小收益中的最大收益，然后将棋下到那个位置即可。

我们直接通过几个有趣的leetcode上面的例子来说明如何去思考。

375. Guess Number Higher or Lower II

题目

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

思路

考虑dp[i][j]表示从i（包含）到j（包含）pick某个数的情况下，保证赢所需要的最少的花费。那么可以知道：

对于每个i<k<j，需要花费k+max(dp[i][k-1], dp[k+1][j])，这里的max表示pick的数在最糟（最小花费最大）的那种情况里；
遍历k，使得dp[i][j]=min(dp[i][j], k+max(dp[i][k-1], dp[k+1][j]))，这里的min表示在最糟的情况下，花费最小

代码

class Solution {
public:
    int getMoneyAmount(int n) {
        vector<vector<int>> dp(n+1, vector<int>(n+1, 0));
        for(int j=2;j<=n;j++){
            for(int i=j-1;i>0;i--){
                dp[i][j] = INT_MAX;
                for(int k=i+1;k<j;k++){
                    dp[i][j] = min(dp[i][j], k+max(dp[i][k-1], dp[k+1][j]));
                }
                if(i+1==j)
                    dp[i][j] = i;
            }
        }
        return dp[1][n];
    }
};

464. Can I Win

题目

https://leetcode.com/problems/can-i-win/#/description

思路

这是一个双人博弈，每次考虑在对手收益最大的情况下，选出让自己收益最大的情况。

代码

class Solution {
public:
    bool canIWin(int maxChoosableInteger, int desiredTotal) {
        unordered_map<unsigned int, bool> dp;
        if(maxChoosableInteger>=desiredTotal)
            return true;
        if((maxChoosableInteger+1)*maxChoosableInteger/2<desiredTotal)
            return false;
        int record = (1<<(maxChoosableInteger+1)) - 1;
        return play(desiredTotal, record, maxChoosableInteger, dp);
    }
    bool play(int dt, int rec, int& size, unordered_map<unsigned int, bool>& dp){
        if(dp.count(rec))
            return dp[rec];
        for(int i=1;i<=size;i++){
            int bit = 1<<i;
            if(bit&rec){
                if(i>=dt)
                    return true;
                bool tmp = play(dt-i, rec^bit, size, dp);
                dp[rec^bit] = tmp;
                if(tmp==false)
                    return true;
            }
        }
        return false;
    }
};

486. Predict the Winner

题目

https://leetcode.com/problems/predict-the-winner/#/description

思路

同第二题

代码

class Solution {
public:
    bool PredictTheWinner(vector<int>& nums) {
        unordered_map<unsigned int, int> dp;
        int l = 0, r = nums.size() - 1;
        return play(dp, l, r, nums) >= 0;
    }
    int play(unordered_map<unsigned int, int>& dp, int l, int r, vector<int>& nums) {
        int state = (1<<l) + (1<<r);
        if(l == r)
            return nums[l];
        if(dp.count(state))
            return dp[state];
        int lFirst = play(dp, l+1, r, nums);
        int rFirst = play(dp, l, r-1, nums);
        int score = max(-lFirst + nums[l], -rFirst + nums[r]);
        dp[state] = score;
        return score;
    }
};