486. 预测赢家

== 石子游戏
给定一个表示分数的非负整数数组。 玩家 1 从数组任意一端拿取一个分数，随后玩家 2 继续从剩余数组任意一端拿取分数，然后玩家 1 拿，…… 。每次一个玩家只能拿取一个分数，分数被拿取之后不再可取。直到没有剩余分数可取时游戏结束。最终获得分数总和最多的玩家获胜。
给定一个表示分数的数组，预测玩家1是否会成为赢家。你可以假设每个玩家的玩法都会使他的分数最大化。

输入：[1, 5, 2]
输出：False
解释：一开始，玩家1可以从1和2中进行选择。
如果他选择 2（或者 1 ），那么玩家 2 可以从 1（或者 2 ）和 5 中进行选择。如果玩家 2 选择了 5 ，那么玩家 1 则只剩下 1（或者 2 ）可选。
所以，玩家 1 的最终分数为 1 + 2 = 3，而玩家 2 为 5 。
因此，玩家 1 永远不会成为赢家，返回 False 。
image.png
image.png

  1. //区间dp模板
  2. func PredictTheWinner(nums []int) bool {
  3.     L := len(nums)
  4.     dp := make([][]int, L)
  5.     for i := 0; i < L; i++ {
  6.         dp[i] = make([]int, L)        //当前玩家与另一个玩家的分数之差的最大值
  8.     }
  9.     for i := 0; i < L; i++ {
  10.         dp[i][i] = nums[i]
  11.     }
  12.     for i := L - 2; i >= 0; i-- { 
  13.         for j := i + 1; j < L; j++ {
  14.             pickI := nums[i] - dp[i + 1][j]            //当前数值 - 前一个人选的总数值
  15.             pickJ := nums[j] - dp[i][j - 1]
  16.             dp[i][j] = max(pickI, pickJ)
  17.         }
  18.      }
  19.     return dp[0][L-1] >= 0
  20. }
  22. func max(a, b int) int {
  23.     if a > b { return a }
  24.     return b
  25. }
//空间优化版，降维
func PredictTheWinner(nums []int) bool {
    n := len(nums)
    dp := make([]int, length)

    for i := 0; i < n; i++ {
        dp[i] = nums[i]
    }
    for i := n - 2; i >= 0; i-- {
        for j := i + 1; j < n; j++ {
            dp[j] = max(nums[i] - dp[j], nums[j] - dp[j - 1])
        }
    }
    return dp[n - 1] >= 0
}

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}