推 sustainer123: dp週 我去死 08/20 20:31
→ JIWP: 我也去死 08/20 20:33
推 dont: 大師 08/20 22:12
怎麼一直dp我要死了
1140. Stone Game II
有一列石頭堆:piles
alice 和 bob兩個人每一次各從piles裡面拿走前x堆的石頭
其中1<=x<=2m，拿完後m=max(m,x)
一開始m為1
由alice先拿，在兩人都採取最佳策略的情況下
alice可以拿多少石頭
思路:
先建立一個suffix sum array
用一個function : calculate去計算在piles[i]且x=j的時候可以拿到最多的石頭數量
function calculate(位置,m)
用二維dp矩陣去紀錄石頭數量
dp[i][j]代表在piles[i] x=j的時候可以拿到的最多石頭數量
要把每個可能的x都計算過
且dp[i][j]=max(dp[i][j],suffixsum[i]-calculate(i+x,max(x,m)))
因為一開始的位置是0且m=1
所以回傳calculate(0,1)就可以得到答案了
golang code :
type solver struct {
n int
dp [][]int
suffsum []int
}
func create(piles []int) *solver {
n := len(piles)
suffsum := make([]int, n+1)
dp := make([][]int, n)
for i := n-1; i > -1; i-- {
suffsum[i] = suffsum[i+1] + piles[i]
}
for i := 0; i < n; i++ {
dp[i] = make([]int, n+1)
for j := 0; j < n; j++ {
dp[i][j] = -1
}
}
return &solver{n, dp, suffsum}
}
func (player *solver) calculate(start, m int) int {
if start >= player.n {
return 0
}
res := player.dp[start][m]
if res > 0 {
return res
}
suffsum := player.suffsum[start]
for i := 1; i <= 2*m; i++ {
res = max(res, suffsum-player.calculate(start+i, max(i,m)))
}
player.dp[start][m] = res
return res
}
func stoneGameII(piles []int) int {
player := create(piles)
return player.calculate(0, 1)
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.73.85.180 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1724157034.A.4DF.html