LeetCode-Go/leetcode/1690.Stone-Game-VII/1690. Stone Game VII.go

package leetcode

// 解法一 优化空间版 DP
func stoneGameVII(stones []int) int {
	n := len(stones)
	sum := make([]int, n)
	dp := make([]int, n)
	for i, d := range stones {
		sum[i] = d
	}
	for i := 1; i < n; i++ {
		for j := 0; j+i < n; j++ {
			if (n-i)%2 == 1 {
				d0 := dp[j] + sum[j]
				d1 := dp[j+1] + sum[j+1]
				if d0 > d1 {
					dp[j] = d0
				} else {
					dp[j] = d1
				}
			} else {
				d0 := dp[j] - sum[j]
				d1 := dp[j+1] - sum[j+1]
				if d0 < d1 {
					dp[j] = d0
				} else {
					dp[j] = d1
				}
			}
			sum[j] = sum[j] + stones[i+j]
		}
	}
	return dp[0]
}

// 解法二 常规 DP
func stoneGameVII1(stones []int) int {
	prefixSum := make([]int, len(stones))
	for i := 0; i < len(stones); i++ {
		if i == 0 {
			prefixSum[i] = stones[i]
		} else {
			prefixSum[i] = prefixSum[i-1] + stones[i]
		}
	}
	dp := make([][]int, len(stones))
	for i := range dp {
		dp[i] = make([]int, len(stones))
		dp[i][i] = 0
	}
	n := len(stones)
	for l := 2; l <= n; l++ {
		for i := 0; i+l <= n; i++ {
			dp[i][i+l-1] = max(prefixSum[i+l-1]-prefixSum[i+1]+stones[i+1]-dp[i+1][i+l-1], prefixSum[i+l-2]-prefixSum[i]+stones[i]-dp[i][i+l-2])
		}
	}
	return dp[0][n-1]
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}