首页 > 代码库 > 从数组两头抽取元素游戏
从数组两头抽取元素游戏
给定一个数组，玩家A,B每次从数组头或尾取数，且只能从头尾取。假定A，B都绝顶聪明，均采取最优策略，判断A先手的情况下，A是否能够获胜。
分析: f(i, j) 表示 在arr[i~j]中A 先手时能够获得的最大分数，s(i, j) 表示 A后手时能够获得的最大分数。
首先分析f(i, j)。 A可先取arr[i], 取完后剩余arr[i+1, j]。此时相当于A后手在[i+1, j]的情况了。
也可先取arr[j], 取完后剩余arr[i, j - 1]。 此时相当于A后手在[i, j -1]的情况了。
则 f(i, j) = max{arr[i] + s(i+1, j), arr[j] + s(i, j-1)}
再分析s（i, j）。B可先取arr[i] 或 arr[j] 。取完后相当于A先手的情况了。只是在这种情况下，B会留下最差解。
s(i, j) = min{arr[i] + f(i+1, j), arr[j] + f(i, j-1)};
故可生成两个二维矩阵。代码如下：
边界条件：
f[j][j] = arr[j]; 因为只有一个数，先手必取这个数。
public static int win2(int[] arr) {
if (arr == null || arr.length == 0) {
return 0;
}
int[][] f = new int[arr.length][arr.length];
int[][] s = new int[arr.length][arr.length];
for (int j = 0; j < arr.length; j++) {
f[j][j] = arr[j];
for (int i = j - 1; i >= 0; i--) {
f[i][j] = Math.max(arr[i] + s[i + 1][j], arr[j] + s[i][j - 1]);
s[i][j] = Math.min(f[i + 1][j], f[i][j - 1]);
}
}
return f[0][arr.length - 1], s[0][arr.length - 1];
}
上述方法时间复杂度O（N2），用到了两个二维数组。可以在空间复杂度上稍微优化一下，只使用1个二维数组。
用dp[i][j]表示在arr[i~j]中A先手的情况能取得的最大分数。则A的这一次先手与下一次先手有4种可能：
1. A 取 arr[i], B 取 arr[j] ， 剩下[i+1, j-1]
2. A 取 arr[i]， B 取arr[i+1]， 剩下[i+2, j]
3. A 取 arr[j]， B 取arr[i]， 剩下[i+1, j-1]
4. A 取arr[j] ， B 取arr[j-1]， 剩下[i, j-2]
前两种情况取最小情况，后两种情况取最小情况，然后取最大值。其实就是综合之前的情况。
边界条件：
i == j时，就是取arr[i]; 同时，此种情况必须保证j >= i +2, 即至少有3个数。代码如下：
public static int win1(int[] arr){
if(arr == null || arr.length == 0)
return 0;
int len = arr.length;
int[][] dp = new int[len][len];
int part1, part2, part3, part4;
for(int i = 0; i < len; i++)
dp[i][i] = arr[i];
for(int i = len - 1; i >= 0; i--)
for(int j = i+1; j < len; j++){
if( j >= i+2 ){
part1 = ( i <= len -3 ? (arr[i] + dp[i+2][j]) : 0 );
part2 = ((i <= len -2 && j >= 1) ? (arr[i] +dp[i+1][j]) : 0);
part3 = (j >= 2 ? (arr[j] + dp[i][j-2]) : 0);
part4 = ((j >= 1 && i <= len-2) ? (arr[j] + dp[i+1][j-1]) : 0);
dp[i][j] = Math.max(Math.min(part1, part2), Math.min(part3, part4));
}else
dp[i][j] = Math.max(arr[i], arr[j]);
}
return dp[0][len-1];
}
从数组两头抽取元素游戏