LeetCode总结——Minimax算法

总结在解决博弈问题中会用到的一个算法——Minimax算法

什么是Minimax算法

什么是Minimax，它是用在决策轮、博弈论和概率论中的一条决策规则。它被用来最小化最坏情况下的可能损失。“最坏”情况是对手带来的最坏情况，“最小”是我要执行的一个最优策略的目标。

实际使用中一般，DFS来遍历当前局势以后所有可能的结果，通过『最大化』自己和『最小化』对手的方法获取下一步的动作。

LeetCode 486

给定一个数组，双方轮流从数组的两边取出一个数，判断最后谁取的数多。

这是一个博弈问题，站在我的角度一定是要使自己的收益最大，但是站在对方的角度一定是要使我的收益最小。此时我们可以用f[i][j]表示我方在i~j这个数组下的收益，s[i][j]表示对方从两边拿了一个数以后我方的收益。此时不难得出状态转移方程：f[i][j] = max(nums[i] + s[i+1][j], nums[j] + s[i][j-1]) 和 min(f[i+1][j], f[i][j-1])

代码：

class Solution {
public:
    // Minimax 算法
    bool PredictTheWinner(vector<int>& nums) {
        int len = nums.size();
        if(len == 0) return true;
        vector<vector<int> > f(len, vector<int>(len, 0)), s(len, vector<int>(len, 0));
        int sum = 0;
        for(int i : nums) sum += i;
        for(int j = 0; j < len; j++)
        {
            f[j][j] = nums[j];
            for(int i = j-1; i >= 0; i--)
            {
                f[i][j] = max(nums[i] + s[i+1][j], nums[j] + s[i][j-1]);
                s[i][j] = min(f[i+1][j], f[i][j-1]);
            }
        }
        return f[0][len-1] >= (sum+1)/2;
    }
};

LeetCode 375

题意：某人从1~n中选一个数k，你每次给出一个数x，他会告诉你x与n的关系(大于，小于或等于)，每次询问你都需要花费x的代价，问你至少需要花费多少钱才能保证查找到k是多少。

一道比较典型的Minimax题目，最小化最大值，当确定中间的一个数x的时候，为了保证找到k一定是选取两边的代价中最大的。但是你可以选取这个x时，你可以选取一个代价最小的x。dp[i][j]表示从i到j猜出值所需要的代价，这时我们可以得到状态转移方程：dp[i][j] = min(x + max(dp[i][k-1], dp[k+1][j]) ) {i <= k <= j}

代码：

class Solution {
public:
    // Minimax算法，dp思路
    int getMoneyAmount(int n) {
        vector<vector<int> > dp(n + 1, vector<int>(n + 1, INT_MAX));
        for(int i = 0; i <= n; i++)
            for(int j = 0; j <= n; j++)
            {
                if(i == j) dp[i][j] = 0;
                else if (i > j) dp[i][j] = 0;
            }
        for(int i = 1; i <= n; i++)
            for(int j = 0; j <= n-i; j++)
            {
                int tem = INT_MAX;
                for(int k = j; k <= j+i; k++)
                {
                    if(k == 0)
                        tem = min(tem, k + dp[k+1][j+i]);
                    else if(k == n)
                        tem = min(tem, k + dp[j][k-1]);
                    else
                        tem = min(tem, k + max(dp[j][k-1], dp[k+1][j+i]));
                }
                dp[j][j+i] = tem;
            }
        return dp[0][n];
    }
};

LeetCode 464

题意：给定两个数m和target，两人依次从1到m的m个数中取出一个数，当轮到的人取出一个数以后使得所有取出的数不小于target这个人就获胜了，判断第一个取的能不能取得游戏的胜利

按照Minimax的思路，当我方作出决策的时候一定作出的是最我方损失最小的决策。当我方所在一个状态数组（1到m中各个数的取出状态数组）和一个target的时候，这个时候我们要做的是从这个状态数组中标记一个数为拿出状态，使得其大于target或者使得轮到对方决策后一定是输。

这里比较棘手的就是这个状态数组了，但是题目给了一个条件，m的值不会超过20个，这个时候我们就可以做一个状态压缩——用status一个数表示整个状态数组：那么这个时候我们就可以得到状态转移方程：dp[n][status] = ((1 << x) & status) == 0 && (x >= n || dp[n-x][status | (1 << x)])，其中((1 << x) & status)表示当前选择的数x是否被选择过；status | (1 << x)表示选择了x以后的状态数组的状态

虽然得到状态转移方程，但是我们不好通过遍历求解，这个时候就可以将动态规划“退化”成递归加上状态记录。这里dp按理说是一个二维数组，但是status和n是有关系的，n表示的是总数减去其取出的数。这里使用map来表示这个dp数组，因为能够表示出三种状态：没有访问过、true、false

代码：

class Solution {
private:
    int n;
    map<int, bool> dp;
    
public:
    // Minimax算法思想，最小化对手的收益
    bool canIWin(int maxChoosableInteger, int desiredTotal) {
        n = maxChoosableInteger;
        if(n >= desiredTotal) return true;
        if((1 + n) * n / 2 < desiredTotal) return false;
        return solute(desiredTotal, 0);
    }
    
    // 因为status和nowNum是有关联关系的，所以map中需要一个
    bool solute(int nowNum, int status) {
        if(dp.find(status) != dp.end()) return dp[status];
        for(int i = 1; i <= n; i++)
        {
            int tem = (1 << i);
            if((tem & status) == 0 && (i >= nowNum || !solute(nowNum - i, tem | status)))
            {
                dp[status] = true;
                return true;
            }
        }
        dp[status] = false;
        return false;
    }
};