leetcode-go/leetcode/medium/486.predict-the-winner.go

func PredictTheWinner(nums []int) bool {
	n := len(nums)
	dp := make([][][]int, n)
	for i := range dp {
		dp[i] = make([][]int, n)
	}
	for i := 0; i < n; i++ {
		dp[i][i] = []int{0, nums[i]}
	}
	for l := 2; l <= n; l++ {
		for i := 0; i < n-l+1; i++ {
			init, tail := dp[i][i+l-2], dp[i+1][i+l-1]
			t := l % 2
			score := make([]int, 2)
			if nums[i]+tail[t]-tail[1-t] <= nums[i+l-1]+init[t]-init[1-t] {
				score[t], score[1-t] = nums[i+l-1]+init[t], init[1-t]
			} else {
				score[t], score[1-t] = nums[i]+tail[t], tail[1-t]
			}
			dp[i][i+l-1] = score
		}
	}
	t := n % 2
	return dp[0][n-1][1-t] <= dp[0][n-1][t]
}