2021-02-15：給定一個(gè)整型數(shù)組arr，代表數(shù)值不同的紙牌排成一條線。玩家A和玩家B依次拿走每張紙牌，規(guī)定玩家A先拿，玩家B后拿。但是每個(gè)玩家每次只能拿走最左或最右的紙牌，玩家A和玩家B都絕頂聰明。請(qǐng)返回最后獲勝者的分?jǐn)?shù)。
福哥答案2021-02-15：
這道題直接背，用自然智慧很難想到，平時(shí)需要鍛煉敏感度。
1.遞歸。有代碼。
先手 依賴(lài) 后手遞歸加數(shù)組元素的最大值。
后手 依賴(lài) 先手遞歸的最小值。
為了方便記憶，先手選大的，后手被迫選小的。實(shí)際上，先手和后手都是盡自己的努力選大的。這表面上看起來(lái)是違背了自然智慧的。
2.動(dòng)態(tài)規(guī)劃。有代碼。
先手dp依賴(lài)【后手左】和【后手下】。
后手dp依賴(lài)【先手左】和【先手下】。
代碼用golang編寫(xiě)，代碼如下：
package main
import "fmt"
func main() {
ret := win1([]int{5, 7, 4, 5, 8, 1})
fmt.Println("1.遞歸：", ret)
ret = win2([]int{5, 7, 4, 5, 8, 1})
fmt.Println("2.動(dòng)態(tài)規(guī)劃：", ret)
}
// 根據(jù)規(guī)則，返回獲勝者的分?jǐn)?shù)
func win1(arr []int) int {
if len(arr) == 0 {
return 0
}
first := f1(arr, 0, len(arr)-1)
second := g1(arr, 0, len(arr)-1)
return getMax(first, second)
}
// arr[L..R]，先手獲得的最好分?jǐn)?shù)返回
func f1(arr []int, L int, R int) int {
if L == R {
return arr[L]
}
p1 := arr[L] + g1(arr, L+1, R)
p2 := arr[R] + g1(arr, L, R-1)
return getMax(p1, p2)
}
// // arr[L..R]，后手獲得的最好分?jǐn)?shù)返回
func g1(arr []int, L int, R int) int {
//if L == R {
// return arr[L]
//}
//p1 := arr[L] + f1(arr, L+1, R)
//p2 := arr[R] + f1(arr, L, R-1)
//return getMin(p1, p2)
if L == R {
return 0
}
p1 := f1(arr, L+1, R) // 對(duì)手拿走了L位置的數(shù)
p2 := f1(arr, L, R-1) // 對(duì)手拿走了R位置的數(shù)
return getMin(p1, p2)
}
func win2(arr []int) int {
if len(arr) == 0 {
return 0
}
N := len(arr)
fmap := make([][]int, N)
gmap := make([][]int, N)
for i := 0; i < N; i++ {
fmap[i] = make([]int, N)
gmap[i] = make([]int, N)
}
for i := 0; i < N; i++ {
fmap[i][i] = arr[i]
}
for startCol := 1; startCol < N; startCol++ {
L := 0
R := startCol
for R < N {
fmap[L][R] = getMax(arr[L]+gmap[L+1][R], arr[R]+gmap[L][R-1])
gmap[L][R] = getMin(fmap[L+1][R], fmap[L][R-1])
L++
R++
}
}
return getMax(fmap[0][N-1], gmap[0][N-1])
}
func getMax(a int, b int) int {
if a > b {
return a
} else {
return b
}
}
func getMin(a int, b int) int {
if a < b {
return a
} else {
return b
}
}
執(zhí)行結(jié)果如下：
圖片
