范圍上嘗試的模型
給定一個整型陣列arr，代表數值不同的紙牌排成一條線，玩家A和玩家B依次拿走每張紙牌，規定玩家A先拿，玩家B后拿，但是每個玩家每次只能拿走最左或最右的紙牌，玩家A和玩家B都絕頂聰明，請回傳最后獲勝者的分數，
博弈論：雙方玩家都不會在對方單獨改變策略的情況下讓對方獲得最大收益
其它類似的零和博弈問題：鱷魚吃人、海盜分金幣、歐拉信封等等
package com.harrison.class12;
public class Code07_CardsInLine {
public static int f(int[] arr,int L,int R) {
// 如果只剩下一張牌了，又是先手，那就直接拿走最后一張
if(L==R) {
return arr[L];
}
// 如果先手拿的是左邊的牌，那么后手只能在[L+1,R]上拿牌
// 如果先手拿的是右邊的牌，那么后手只能在[L,R-1]上拿牌
// 這兩種情況下，先手肯定會只選擇對自己最有利的方式，也就是回傳最大值
return Math.max(arr[L]+s(arr, L+1, R), arr[R]+s(arr, L, R-1));
}
public static int s(int[] arr,int L,int R) {
// 如果只剩下一張牌了，又是后手，那就沒牌拿
if(L==R) {
return 0;
}
// 因為是后手，所以沒得選，只能選得分最少的方式
// 得分多的方式被先手給選了
return Math.min(f(arr, L+1, R), f(arr, L, R-1));
}
public static void main(String[] args) {
int[] arr= {4,7,9,5};
System.out.println(f(arr, 0, 3));
System.out.println(s(arr, 0, 3));
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/395117.html
標籤：其他
上一篇：前端的同學不會還在用VS Code吧，可以放棄了；小馬帶你認識前端開發神器WebStorm（WebStorm及Git的相關配置與使用）
下一篇：微燈手握寸筆，細談記憶體管理