?取数对弈是一道经典的面试题，思路是动态规划求解，通过求解子问题推导最终的结果.

1. 取数对弈问题

取数对弈问题是 google 的一道面试题, 题目描述如下:

取数对弈游戏问题：
?
取数游戏是一个 2 人对策游戏。游戏开始时将 n 个数在棋盘上从左到右排成一行。
甲乙双方轮流在这一行数的左右两端取数，直至全部取完 n 个数。每人所取得的数的
总为其得分值。
?
最后双方得分多者获胜.（游戏规定由甲方先取数.）

这里，甲乙双方都采用如下最优策略:
1)甲每次取都希望取到的这个数使自己得分最高
2)乙每次取都希望取到的这个数令甲的得分最低

请编程实现：在甲乙双方都采用最优策略的前提下，计算甲方先取数时双方的最后
得分.

解题思路:

这个题目中，甲乙双方都是按照最优策略取数的，即当一方先取数时，另一方将会变成另一个取数对弈问题的先取数者.

如果这里只有 2 个数, 显然取最大的即可, 结局是唯一的. 那么变成 3 个数呢? 甲方取一个数后，问题变成 2 个数的乙方先取的问题了. 很显然，这个问题中，双方均以自己得分最高，对方得分最低为目标，那么 2 个数是固定策略，3 个数时也是固定取法，4 个、5 个、6 个... n 个数都将是固定的取法. 即在最优策略下，得分是唯一的.

通过分析可以知道，我们需要通过子数组推断最终的数组的得分，因为1个、2个数组的答案是显然易见的，就可以依次推断出 3 个、4个、n个数的数组的最终得分了. 令 p[i][j] 为第 i 个数到第 j 个数组成的数组，先取数者采用最优策略取数的得分, sum[i][j] 为第 i 个数到第 j 个数的和. 则可以将 n 个数的问题变成 n-1 个数的子数组问题，公式如下:

p[i][j] = sum[i][j] - max(p[i+1][j], p[i][j-1])

下面是代码实现

// golang
func sum(i int, j int, nums []int) int {
   res := 0
   for i <= j {
      res += nums[i]
      i++
   }
   return res
}

func min(i, j int) int {
   if i < j {
     return i
   }
   return j
}

func score(nums []int) int {
    n := len(nums)
    if n < 1 {
       return 0
    }
    if n < 2 {
      return nums[0]
    }
    p := make([][]int, n)
    for i := 0; i < n ; i++ {
       p[i] = make([]int, n)
       p[i][i] = nums[i]
    }

    // 计算 i, j 子数组的结果, p[i][j] 需要用到 i,j 内的子数组
    // 所以从小范围子数组开始计算
    for i := n - 2;i >= 0; i-- {
      // 计算 i 后面的子数组
      for j := i+1; j < n ; j++ {
          p[i][j] = sum(i, j, nums) - min(p[i][j-1], p[i+1][j])          
      }
  }
  return p[0][n-1]
}

2. leetcdoe 486. Predict the Winner

Leetcode 的 486 便是取数对弈问题，这个题目同样也是取数，最终判断先取数的是否能保证一定能赢.

题目描述如下:

Given an array of scores that are non-negative integers. Player 1 picks one of the numbers from either end of the array followed by the player 2 and then player 1 and so on. Each time a player picks a number, that number will not be available for the next player. This continues until all the scores have been chosen. The player with the maximum score wins.

Given an array of scores, predict whether player 1 is the winner. You can assume each player plays to maximize his score.

Example 1:

Input: [1, 5, 233, 7]
Output: True
Explanation: Player 1 first chooses 1. Then player 2 have to choose between 5 and 7. No matter which number player 2 choose, player 1 can choose 233.
Finally, player 1 has more score (234) than player 2 (12), so you need to return True representing player1 can win.

Example 2:

Input: [1, 5, 233, 7]
Output: True
Explanation: Player 1 first chooses 1. Then player 2 have to choose 
between 5 and 7. No matter which number player 2 choose, player 1 can 
choose 233.Finally, player 1 has more score (234) than player 2 (12), 
  so you need 
to return True representing player1 can win.

显然将上述代码稍加改造即可，最终比较甲乙双方得分的结果即可，代码如下:

// golang
func PredictTheWinner(nums []int) bool {
    n := len(nums)
    if n < 1 {
       return false
    }
    if n < 2 {
      return true
    }
    p := make([][]int, n)
    for i := 0; i < n; i++ {
       p[i] = make([]int, n)
       p[i][i] = nums[i]
    }
    
    // 计算 i, j 子数组的结果, p[i][j] 需要用到 i,j 内的子数组
    // 所以从小范围子数组开始计算
    for i := n - 2;i >= 0; i-- {
      // 计算 i 后面的子数组
      for j := i+1; j < n ; j++ {
          p[i][j] = sum(i, j, nums) - min(p[i][j-1], p[i+1][j])          
      }
    }
    return p[0][n-1] >= (sum(0, n-1, nums) - p[0][n-1])
}

func sum(i int, j int, nums []int) int {
   res := 0
   for i <= j {
      res += nums[i]
      i++
   }
   return res
}

func min(i, j int) int {
   if i < j {
     return i
   }
   return j
}

3. 参考资料

1.Predict the winner [https://leetcode.com/problems/predict-the-winner/]

2.9717 取数对弈 [https://www.cnblogs.com/double891/p/8082087.html]