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])

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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}

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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;
}
};