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