动态规划

tech2022-10-06  107

🌸题目

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

给定一个表示分数的数组,预测玩家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 。

示例 2:

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

提示:

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

分析

首先分析就是使用递归

🌸方法一:暴力递归(正常思路)

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); } }

🌸方法二:递归(思路一)

🍁分析

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

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

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

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 分作比较,判断出胜利。

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

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

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]。我们用数组或哈希表去存储计算过的子问题的解,下次遇到重复的子问题,就不用再次递归计算。

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]; }

🌸方法五:动态规划

🍁分析

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

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

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

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

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

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

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; }

🌸方法六:动态规划优化

🍁分析

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

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; }

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

最新回复(0)