思路來(lái)源于labuladong老師的公眾號(hào)崇裁，本文僅用于個(gè)人學(xué)習(xí)整理
亞歷克斯和李用幾堆石子在做游戲哀澈。偶數(shù)堆石子排成一行滓窍，每堆都有正整數(shù)顆石子 piles[i] 与帆。
游戲以誰(shuí)手中的石子最多來(lái)決出勝負(fù)了赌。石子的總數(shù)是奇數(shù)，所以沒(méi)有平局玄糟。
亞歷克斯和李輪流進(jìn)行揍拆，亞歷克斯先開(kāi)始。 每回合茶凳，玩家從行的開(kāi)始或結(jié)束處取走整堆石頭嫂拴。 這種情況一直持續(xù)到?jīng)]有更多的石子堆為止，此時(shí)手中石子最多的玩家獲勝贮喧。
假設(shè)亞歷克斯和李都發(fā)揮出最佳水平筒狠，當(dāng)亞歷克斯贏得比賽時(shí)返回 true ，當(dāng)李贏得比賽時(shí)返回 false
博弈問(wèn)題箱沦，先手與后手會(huì)對(duì)互相產(chǎn)生影響辩恼。
首先定義dp數(shù)組的含義，有piles[i...j]這個(gè)數(shù)組谓形，dp[i][j]即為在i到j(luò)這些石子中能獲得的最高分?jǐn)?shù)灶伊，先手后手分別存在dp數(shù)組中，故可以定義一個(gè)結(jié)構(gòu)體
class Pair {
public int fir;
public int sec;
public Pair(int fir, int sec) {
this.fir = fir;
this.sec = sec;
}
}
dp[i][j].fir即為先手可以拿到的最高分?jǐn)?shù)寒跳，sec即為后手拿到的最高分?jǐn)?shù)
狀態(tài)轉(zhuǎn)移方程：dp[i][j].fir=max(piles[i]+dp[i+1][j].sec,pile[j]+dp[i][j-1].sec)
if 先手選擇左邊
dp[i][j].sec=dp[i+1][j].fir
else
dp[i][j].sec=dp[i][j-1].fir
base case:當(dāng)i=j時(shí)聘萨，dp數(shù)組對(duì)應(yīng)元素應(yīng)該dir=piles[i]，sec=0
此外要斜著遍歷數(shù)組
package dp;
public class stoneGame {
class Pair {
public int fir;
public int sec;
public Pair(int fir, int sec) {
this.fir = fir;
this.sec = sec;
}
}
boolean stoneGame(int[] piles) {
int n = piles.length;
Pair[][] dp = new Pair[n][n];
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
dp[i][j] = new Pair(0, 0);
}
}
for (int i = 0; i < n; i++) {
dp[i][i].fir = piles[i];
dp[i][i].sec = 0;
}
for (int l = 2; l <= n; l++) {
for (int i = 0; i <= n - l; i++) {
int j = l + i - 1;
int left = piles[i] + dp[i + 1][j].sec;
int right = piles[j] + dp[i][j - 1].sec;
if (left > right) {
dp[i][j].fir = left;
dp[i][j].sec = dp[i + 1][j].fir;
} else {
dp[i][j].fir = right;
dp[i][j].sec = dp[i][j - 1].fir;
}
}
}
Pair res = dp[0][n - 1];
if(res.fir>0){
return true;
}else{
return false;
}
}
public static void main(String[] args) {
int []piles=new int[]{5,3,4,5};
System.out.println(new stoneGame().stoneGame(piles));
}
}
其中斜著遍歷數(shù)組用了三個(gè)變量實(shí)現(xiàn)童太，很有意思
