怎麼一直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