题目描述
给你一个整数数组 nums 。玩家 1 和玩家 2 基于这个数组设计了一个游戏。
玩家 1 和玩家 2 轮流进行自己的回合，玩家 1 先手。开始时，两个玩家的初始分值都是 0 。每一回合，玩家从数组的任意一端取一个数字（即，nums[0] 或 nums[nums.length - 1]），取到的数字将会从数组中移除（数组长度减 1 ）。玩家选中的数字将会加到他的得分上。当数组中没有剩余数字可取时，游戏结束。
如果玩家 1 能成为赢家，返回 true 。如果两个玩家得分相等，同样认为玩家 1 是游戏的赢家，也返回 true 。你可以假设每个玩家的玩法都会使他的分数最大化。
示例 1：
- 输入：nums = [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 。
示例 2：
- 输入：nums = [1,5,233,7]
- 输出：true
- 解释：玩家 1 一开始选择 1 。然后玩家 2 必须从 5 和 7 中进行选择。无论玩家 2 选择了哪个，玩家 1 都可以选择 233 。最终，玩家 1（234 分）比玩家 2（12 分）获得更多的分数，所以返回 true，表示玩家 1 可以成为赢家。
提示：
1 <= nums.length <= 20- 0 <= nums[i] <= 107
解法一：递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
func max(nums ...int) int {
res := nums[0]
for _, num := range nums {
if num > res {
res = num
}
}
return res
}
func PredictTheWinner(nums []int) bool {
n := len(nums)
// recur(start, end) 返回选择数组 nums 在 [start, end] 之间的元素时
// 先手能够获得的最大总分 减去 后手玩家能够获得的最大总分的 最大值
var recur func(start, end int) int
recur = func(start, end int) int{
if start == end {
return nums[start]
}
planA := nums[start] - recur(start+1, end)
planB := nums[end] - recur(start, end-1)
return max(planA, planB)
}
return recur(0, n-1) >= 0
}
|
解法二：动态规划
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
func max(nums ...int) int {
res := nums[0]
for _, num := range nums {
if num > res {
res = num
}
}
return res
}
func PredictTheWinner(nums []int) bool {
n := len(nums)
var dp [2][]int
// dp[i][j] 表示当数组剩下的部分为下标 i 到下标 j 的元素时
// 先手玩家能够获得的最大总分 减去 后手玩家能够获得的最大总分的最大值
// 当 dp[i][j] >= 0 时，先手玩家可以获胜
dp[0], dp[1] = make([]int, n), make([]int, n)
for i := n - 1; i >= 0; i-- {
for j := i; j < n; j++ {
if i == j {
dp[0][j] = nums[i]
} else {
dp[0][j] = max(nums[i]-dp[1][j], nums[j]-dp[0][j-1])
}
}
dp[1] = dp[0]
}
return dp[0][n-1] >= 0
}
|
