动态规划_leetcode.486.预测赢家

发表于 | 分类于 ， | 热度: ℃
字数统计: 2.3k | 阅读时长 ≈ 9

🌸题目

🍁给定一个表示分数的非负整数数组。 玩家 1 从数组任意一端拿取一个分数，随后玩家 2 继续从剩余数组任意一端拿取分数，然后玩家 1 拿，…… 。每次一个玩家只能拿取一个分数，分数被拿取之后不再可取。直到没有剩余分数可取时游戏结束。最终获得分数总和最多的玩家获胜。

给定一个表示分数的数组，预测玩家1是否会成为赢家。你可以假设每个玩家的玩法都会使他的分数最大化。

示例 1：

1
2
3
4
5
6
输入：[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：

1
2
3
4
输入：[1, 5, 233, 7]
输出：True
解释：玩家 1 一开始选择 1 。然后玩家 2 必须从 5 和 7 中进行选择。无论玩家 2 选择了哪个，玩家 1 都可以选择 233 。
     最终，玩家 1（234 分）比玩家 2（12 分）获得更多的分数，所以返回 True，表示玩家 1 可以成为赢家。

提示：

  • 1 <= 给定的数组长度 <= 20.
  • 数组里所有分数都为非负数且不会大于 10000000 。
  • 如果最终两个玩家的分数相等，那么玩家 1 仍为赢家。

分析

首先分析就是使用递归

🌸方法一：暴力递归（正常思路）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public boolean PredictTheWinner(int[] nums) {
	// 模拟真实情况下，A，B轮流选牌的过程，求出结果
	return dfs(0, nums.length - 1, 0, 0, true, nums);
}
//分别为  左边可取的位置，右边可取的位置，A的得分，B的得分，   轮到谁选牌，   nums数组
private static boolean dfs(int left, int right, int sumA, int sumB, boolean to_A, int[] nums) {
	// TODO Auto-generated method stub
	if(left > right) {//左右越界，没有牌了，比较得分，判断胜负（以A为主角）
		return sumA >= sumB;
	}
	if(to_A) {//轮到A选牌,A是主角，只要左边或者右边有一种必胜情况，就说明可以必胜
		return dfs(left + 1, right, sumA + nums[left], sumB, false, nums) || dfs(left, right - 1, sumA + nums[right], sumB, false, nums);
	}else {//轮到B选牌，不管B怎么选，此时只有左右两边都保证A是必胜的，才能保证A最终必胜
		return dfs(left + 1, right, sumA, sumB+ nums[left], true, nums) && dfs(left, right - 1, sumA, sumB + nums[right], true, nums);
	}
}

🌸方法二：递归（思路一）

🍁分析

为了判断哪个玩家可以获胜，需要计算一个总分，为先手得分与后手得分之差。当数组中的所有数字都被拿取时，如果总分大于或等于 00，则先手获胜，反之则后手获胜。

由于每次只能从数组的任意一端拿取数字，因此可以保证数组中剩下的部分一定是连续的。假设数组当前剩下的部分为下标start 到下标end，其中$ 0 \le \textit{start} \le \textit{end} < \textit{nums}.\text{length}$。如果 $\textit{start}=\textit{end}$，则只剩一个数字，当前玩家只能拿取这个数字。如果$ \textit{start}<\textit{end}$，则当前玩家可以选择 $\textit{nums}[\textit{start}]$ 或 $\textit{nums}[\textit{end}]$，然后轮到另一个玩家在数组剩下的部分选取数字。这是一个递归的过程。

计算总分时，需要记录当前玩家是先手还是后手，判断当前玩家的得分应该记为正还是负。当数组中剩下的数字多于 1 个时，当前玩家会选择最优的方案，使得自己的分数最大化，因此对两种方案分别计算当前玩家可以得到的分数，其中的最大值为当前玩家最多可以得到的分数。

1
2
3
4
5
6
7
8
9
10
11
12
public boolean PredictTheWinner(int[] nums) {
    return total(nums, 0, nums.length - 1, 1) >= 0;
}

public int total(int[] nums, int start, int end, int turn) {
    if (start == end) {
        return nums[start] * turn;
    }
    int scoreStart = nums[start] * turn + total(nums, start + 1, end, -turn);
    int scoreEnd = nums[end] * turn + total(nums, start, end - 1, -turn);
    return Math.max(scoreStart * turn, scoreEnd * turn) * turn;
}

🌸方法三：递归（思路二）

🍁分析

以 [1, 5, 233, 7] 为例，玩家 1 先手。

如果玩家 1 先选左端 1，则玩家 2 在 [5, 233, 7] 的两端中选。
如果玩家 1 先选右端 7，则玩家 2 在 [1, 5, 233] 的两端中选。

可以看到，每个节点都是其中一个玩家在选择。当前子问题下，谁的分数更多，谁就赢。

当前，你选了 x，得 x 分，他没选，得 0分，你赢了别人 x 分，接下来呢？他选，然后你选……你们交替地得分……打住，你已进入递归的细节，别想下去了。

当前你有 x 分，对手 0 分，在后面的游戏中，对手拢共超过你 y 分，如果 x >= y，那你赢咯。

别操心递归的细节，细节丢给子调用去做，眼睛盯着当前的 x 分，想想子调用应该返回什么，去和当前的 x 分作比较，判断出胜利。

于是，递归函数做的事：计算当前做选择的玩家能赢过对手的分数。如果大于零，则表示他在这个子问题中赢了。

怎么计算呢？当前选择的分数，减去，接下来对手赢过自己的分数（剩余数组的递归结果），因为选择有两种，所以我们二者取其大。

1
2
3
4
5
6
7
8
9
10
11
12
public boolean PredictTheWinner2(int[] nums) {
	return help(0, nums.length - 1, nums) >= 0;
}
private static int help(int left, int right, int[] nums) {
	// TODO Auto-generated method stub
	if(left == right) {
		return nums[left];
	}
	int sumL = nums[left] - help(left + 1, right, nums); // 选择左端
	int sumR = nums[right] - help(left, right, nums);// 选择右端
	return Math.max(sumL, sumR);
}

🌸方法四：记忆化递归（思路优化）

🍁分析

我们做了哪些重复的计算呢？
比如，你先选 1，我再选 7，和你先选 7，我再选 1，这两种所带来的子问题是一样的，都是剩下[5, 233]。我们用数组或哈希表去存储计算过的子问题的解，下次遇到重复的子问题，就不用再次递归计算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public static boolean PredictTheWinner3(int[] nums) {
	int len = nums.length;
	int[][] memo = new int[len][len];
	
	for(int i = 0; i < len; i++) {
		Arrays.fill(memo[i], Integer.MIN_VALUE);
	}
	
	return dfs2(nums, 0, len - 1, memo) >= 0;
}
public static int dfs2(int[] nums, int left, int right, int[][] memo) {
	if(left > right) {
		return 0;
	}
	
	if(memo[left][right] != Integer.MIN_VALUE) {
		return memo[left][right];
	}
	int Left = nums[left] - dfs2(nums, left + 1, right, memo);
	int Right = nums[right] - dfs2(nums, left, right - 1, memo);
	memo[left][right] = Math.max(Left, Right);
	return memo[left][right];
}

🌸方法五：动态规划

🍁分析

定义二维数组$\textit{dp}$，其行数和列数都等于数组的长度，$\textit{dp}[i][j]$表示当数组剩下的部分为下标 i 到下标 j 时，当前玩家与另一个玩家的分数之差的最大值，注意当前玩家不一定是先手。

只有当$ i \le j $时，数组剩下的部分才有意义，因此当 $i>j$ 时，$\textit{dp}[i][j]=0$。

当 i=j时，只剩一个数字，当前玩家只能拿取这个数字，因此对于所有 $0 \le i < \textit{nums}.\text{length}$，都有$ \textit{dp}[i][i]=\textit{nums}[i]$。

当 i<j时，当前玩家可以选择 $\textit{nums}[i]$ 或$\textit{nums}[j]$，然后轮到另一个玩家在数组剩下的部分选取数字。在两种方案中，当前玩家会选择最优的方案，使得自己的分数最大化。因此可以得到如下状态转移方程：

$\textit{dp}[i][j]=\max(\textit{nums}[i] - \textit{dp}[i + 1][j], \textit{nums}[j] - \textit{dp}[i][j - 1])
$

最后判断$ \textit{dp}[0][\textit{nums}.\text{length}-1]$ 的值，如果大于或等于 0，则先手得分大于或等于后手得分，因此先手成为赢家，否则后手成为赢家。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static boolean PredictTheWinner4(int[] nums) {
	int len = nums.length;
	int[][] dp = new int[len][len];
	
	for(int i = 0; i < len; i++) {
		dp[i][i] = nums[i];
	}
	for(int i = len - 2; i >= 0; i--) {
		for(int j = i + 1; j < len; j++) {
			dp[i][j] = Math.max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1]);
		}
	}
	return dp[0][len - 1] >= 0;
}

🌸方法六：动态规划优化

🍁分析

上述代码中使用了二维数组 $\textit{dp}$。分析状态转移方程可以看到，$\textit{dp}[i][j$ 的值只和$ \textit{dp}[i + 1][j] $与$ \textit{dp}[i][j - 1] $有关，即在计算$ \textit{dp} $的第 ii 行的值时，只需要使用到 $\textit{dp} $的第 i 行和第 i+1 行的值，因此可以使用一维数组代替二维数组，对空间进行优化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static boolean PredictTheWinner5(int[] nums) {
	int len = nums.length;
	int[] dp = new int[len];
	
	for(int i = 0; i < len; i++) {
		dp[i] = nums[i];
	}
	for(int i = len - 2; i >= 0; i--) {
		for(int j = i + 1; j < len; j++) {
			dp[j] = Math.max(nums[i] - dp[j], nums[j] - dp[j - 1]);
		}
	}
	return dp[len - 1] >= 0;
}

最后，不经历风雨,怎能在计算机的大山之顶看见彩虹呢！ 无论怎样，相信明天一定会更好！！！！！

-------------本文结束感谢您的阅读-------------
云澈 wechat
扫一扫，用手机访问哦
坚持原创技术分享，您的支持将鼓励我继续创作！
0%