紙牌博弈問題
紙牌博弈問題
作者：Grey
原文地址：
題目描述
有一個整型數組 A，代表數值不同的紙牌排成一條線。玩家 a 和玩家 b 依次拿走每張紙牌，
規定玩家 a 先拿，玩家 b 後拿，
但是每個玩家每次只能拿走最左或最右的紙牌，
玩家 a 和玩家 b 都絕頂聰明，他們總會採用最優策略。
請返回最後獲勝者的分數。
註：給定紙牌序列 A 及序列的大小 n，請返回最後分數較高者得分數(相同則返回任意一個分數)。保證 A 中的元素均小於等於1000。且 A 的大小小於等於300。
題目鏈接：牛客-紙牌博弈
暴力遞歸解
定義兩個遞歸函數，第一個遞歸函數是
int first(int[] A, int n, int start, int end)
這個遞歸函數表示的含義是：先手在數組 A 的 start 到 end 範圍內，經過 n 輪，能獲得的最大的分數是多少。
base case 是，當 start == end 的時候，即數組 A 只有一個元素，此時先手直接拿走這個元素，最大分數就是此時先手拿走的唯一元素值，即
if (start == end) {
return A[start];
}
第二個遞歸函數是
int second(int[] A, int n, int start, int end)
這個遞歸函數表示的含義是：後手在數組 A 的 start 到 end 範圍內，經過 n 輪，能獲得的最大的分數是多少。
base case 是，當 start == end 的時候，即數組 A 只有一個元素，此時這個元素肯定要被先手拿走，那麼後手只能返回 0，即
if (start == end) {
return 0;
}
接下來是普遍情況，對於先手函數來說，有兩個位置可以選，一個是 start 位置，另外一個是 end 位置，如果選了 start 位置，那麼先手在下一輪就是後手，即
A[start] + second(A, n, start + 1, end)
同理，如果選 end 位置，先手在下一輪是後手，即
A[end] + second(A, n, start, end - 1)
先手函數在做上述兩個決策的過程中，一定要取最大值，即
Math.max(A[start] + second(A, n, start + 1, end), A[end] + second(A, n, start, end - 1));
所以，先手函數的完整程式碼如下
public static int first(int[] A, int n, int start, int end) {
if (start == end) {
return A[start];
}
return Math.max(A[start] + second(A, n, start + 1, end), A[end] + second(A, n, start, end - 1));
}
接下來是後手函數的普遍情況，對於後手函數來說，沒有先選的權力，只能讓先手選完自己才能選，先手如果選了 start 位置，後手面對的選擇是
first(A, n, start + 1, end)
先手如果選了 end 位置，後手面對的選擇就是
first(A, n, start, end - 1)
後手在下一輪就是先手，所以要保證先手的上述選擇最小，即
Math.min(first(A, n, start + 1, end), first(A, n, start, end - 1));
定義了先手函數和後手函數，主函數做如下調用即可
public static int cardGame(int[] A, int n) {
// 沒有元素，直接返回0分
if (n == 0) {
return 0;
}
// 只有一個元素，無論如何，只能得到 A[0] 分
if (n == 1) {
return A[0];
}
// 只有兩個元素，選最大的那個
if (n == 2) {
return Math.max(A[0], A[1]);
}
// 普遍情況：先手後手中最大的那個
return Math.max(first(A, n, 0, A.length - 1), second(A, n, 0, A.length - 1));
}
超時
動態規劃解
根據上述暴力遞歸函數可知，兩個遞歸函數都可變參數都是 2 個，且可變參數的變化範圍是固定的，所以我們可以用兩個二維數組來分別表示兩個遞歸函數的結果，
// 保存先手函數的遞歸過程解
int[][] firstMap = new int[n][n];
// 保存後手函數的遞歸過程解
int[][] secondMap = new int[n][n];
由於遞歸過程的兩個可變參數 start 和 end 是有範圍的，且 start 不可能大於 end，所以，上述兩個二維數組的左下半區都是無效區域，無需考慮。
在暴力遞歸過程中，當 start == end 的時候，返回 A[start] 值，所以，針對 firstMap，其對角線（start == end）的值都是確定的
// 對角線
for (int i = 0; i < n; i++) {
firstMap[i][i] = A[i];
}
經過上述過程，可以得到兩個二維數組的如下區域的內容
接下來就是普遍情況，
基於暴力遞歸過程可以很方便得到兩個二維數組之間的遞推關係
// 對角線下班區域不用管
// 對角線上半區域
for (int i = 1; i < n; i++) {
int r = 0;
int c = i;
while (c < n) {
firstMap[r][c] = Math.max(A[r] + secondMap[r + 1][c], A[c] + secondMap[r][c - 1]);
secondMap[r][c] = Math.min(firstMap[r + 1][c], firstMap[r][c - 1]);
r++;
c++;
}
}
完整程式碼如下
import java.util.*;
public class Cards {
public static int cardGame(int[] A, int n) {
if (n == 0) {
return 0;
}
if (n == 1) {
return A[0];
}
if (n == 2) {
return Math.max(A[0], A[1]);
}
int[][] firstMap = new int[n][n];
int[][] secondMap = new int[n][n];
// 對角線
for (int i = 0; i < n; i++) {
firstMap[i][i] = A[i];
}
// 對角線下班區域不用管
// 對角線上半區域
for (int i = 1; i < n; i++) {
int r = 0;
int c = i;
while (c < n) {
firstMap[r][c] = Math.max(A[r] + secondMap[r + 1][c], A[c] + secondMap[r][c - 1]);
secondMap[r][c] = Math.min(firstMap[r + 1][c], firstMap[r][c - 1]);
r++;
c++;
}
}
return Math.max(firstMap[0][n - 1], secondMap[0][n - 1]);
}
}
