成都专业做网站公司,昆山的网站建设,河南网站建设网络公司,智慧团建网站官网入口登录给你一个整数数组 nums 。玩家 1 和玩家 2 基于这个数组设计了一个游戏。 玩家 1 和玩家 2 轮流进行自己的回合#xff0c;玩家 1 先手。开始时#xff0c;两个玩家的初始分值都是 0 。每一回合#xff0c;玩家从数组的任意一端取一个数字#xff08;即#xff0c;nums[0]… 给你一个整数数组 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 。 最终玩家 1234 分比玩家 212分获得更多的分数所以返回 true表示玩家 1 可以成为赢家。 提示
1 nums.length 20 0 nums[i] 10^7 解题思路
1、设玩家1得分为正玩家2得分为负最后得分大于等于0则返还true
2、玩家1、2的每次选择都尽量是这局比赛的最优值即最大值
3、由于在搜索过程中难免会出现重复分支所以需要memo数组记录并剪枝
int chooseleft nums[i] - dfs(i 1, j, nums, memo);
int chooseright nums[j] - dfs(i, j - 1, nums, memo);//本次取为正数对手取为负数
以 [1,5,2]为例子解析上述代码的运行过程
2 - (5 - (1 - (0)))代码
import java.util.*;
class Solution {public int INF Integer.MAX_VALUE;public boolean predictTheWinner(int[] nums) {int len nums.length;int memo[][] new int[len][len];for(int i 0; i len; i ) Arrays.fill(memo[i], INF);return dfs(0, len - 1, nums, memo) 0;//平局也算赢}public int dfs(int i, int j, int nums[], int memo[][]) {if(i j) return 0;//结束条件if(memo[i][j] ! INF) return memo[i][j];//memo中存有最优值直接返还。int chooseleft nums[i] - dfs(i 1, j, nums, memo);int chooseright nums[j] - dfs(i, j - 1, nums, memo);//本次取为正数对手取为负数memo[i][j] Math.max(chooseleft, chooseright);//取最优值return memo[i][j];}
}
