预测赢家(力扣)dfs + 备忘录 JAVA

给你一个整数数组 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] <= 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];}
}

在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/84893.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【LeetCode】45. 跳跃游戏 II - 贪婪算法

目录标题 2023-8-11 09:49:25 45. 跳跃游戏 II 2023-8-11 09:49:25 自己没做出来&#xff0c;废物Orz class Solution {public int jump(int[] nums) {int length nums.length;int end 0;int maxPosition 0;int steps 0;for (int i 0; i < length - 1; i) {maxPosit…

首批获得金融级行业云平台认证,天翼云深耕行业云

云计算下半场看什么&#xff1f; 无疑是金融、政务、制造等传统政企用户的上云与用云。随着数字经济发展和产业数字化的提速&#xff0c;上云已是政企用户推动其数字化转型不断深入的重要抓手&#xff0c;成为不可阻挡的趋势。 与互联网用户相比&#xff0c;政企用户上云极为…

从数据仓库到数据结构:数据架构的演变之路

在上个世纪&#xff0c;从电子商务巨头到医疗服务机构和政府部门&#xff0c;数据已成为每家组织的生命线。有效地收集和管理这些数据可以为组织提供宝贵的洞察力&#xff0c;以帮助决策&#xff0c;然而这是一项艰巨的任务。 尽管数据很重要&#xff0c;但CIOinsight声称&…

那些年的Java开发经验记录

Java同步锁(浅显易懂&#xff0c;精简讲解) 详细讲解可以看这篇文章Java对象锁和类锁全面解析&#xff08;多线程synchronized关键字&#xff09; 精简如下&#xff1a; 1.不管什么锁&#xff0c;都是属于对象锁(类也是一种对象) 2.一个对象只有一个锁 3.锁最大可以锁整个…

【框架类】—Vue3的生命周期

一、生命周期的相关函数 onBeforeMount 页面渲染之前 和 onMounted渲染之后 示例 <template><div class"test"><div ref"el">组件初始化</div></div> </template> <script> //按需引入所需方法 import { ref,…

Redux - Redux在React函数式组件中的基本使用

文章目录 一&#xff0c;简介二&#xff0c;安装三&#xff0c;三大核心概念Store、Action、Reducer3.1 Store3.2 Reducer3.3 Action 四&#xff0c;开始函数式组件中使用4.1&#xff0c;引入store4.1&#xff0c;store.getState()方法4.3&#xff0c;store.dispatch()方法4.4&…

04-4_Qt 5.9 C++开发指南_时间日期与定时器

文章目录 1. 时间日期相关的类2. 源码2.1 可视化UI设计2.2 dialog.h2.3 dialog.cpp 1. 时间日期相关的类 时间日期是经常遇到的数据类型&#xff0c;Qt 中时间日期类型的类如下。 QTime:时间数据类型&#xff0c;仅表示时间&#xff0c;如 15:23:13。 QDate:日期数据类型&…

虹科方案 | 汽车总线协议转换解决方案

汽车总线&#xff1a; 汽车总线是一种用于在车辆电子系统中传输数据和控制信息的通信系统。它允许不同的电子控制单元&#xff08;ECU&#xff09;在车辆中相互通信&#xff0c;协调各个系统的操作&#xff0c;以实现功能的集成和协同工作。 在现代汽车中&#xff0c;综合通信…

微信公众号模板消息推送测试Python版无需服务器-保姆级教程

手上有个项目&#xff0c;是服务器挂着自动化的爬虫的&#xff0c;但我用的那个IP代理商没有用尽报警&#xff0c;导致几次IP用尽&#xff0c;程序爬不到数据&#xff0c;进程死循环了。之前想过发邮箱提醒我&#xff0c;但是邮箱把又不及时&#xff0c;老忘记看&#xff0c;因…

C语言必会题目(1)

W...Y的主页 &#x1f60a; 代码仓库分享❤️ 在学习语言时&#xff0c;最重要的就是练习&#xff0c;光听不练假把式。下面我就推荐一些C语言必会的题。 执行下面程序&#xff0c;正确的输出是&#xff08; &#xff09; int x5,y7; void swap() { int z; zx; xy; yz; } int…

数字孪生三剑客来了!MapGIS Earth for Unreal的自述

嗨&#xff0c;大家好&#xff01;我的名字叫MapGIS Earth for Unreal&#xff0c;是MapGIS数字孪生平台产品家族的一员。提起我&#xff0c;大家可能不熟悉&#xff0c;但是提起数字孪生&#xff0c;想必大家倍感兴趣。 数字孪生是充分利用物理模型、传感器更新、运行历史等数…

【git】解决遇到的问题

目录 一、error: RPC failed; curl 6 OpenSSL SSL_read: Connection was reset, errno 10054 二、error: RPC failed; curl 6 OpenSSL SSL_read: Connection was reset, errno 10054 一、error: RPC failed; curl 6 OpenSSL SSL_read: Connection was reset, errno 10054 报…

2023最新Windows编译ffmpeg详细教程,附msys2详细安装配置教程

安装MSYS2 msys2是一款跨平台编译套件&#xff0c;它模拟linux编译环境&#xff0c;支持整合mingw32和mingw64&#xff0c;能很方便的在windows上对一些开源的linux工程进行编译运行。 类似的跨平台编译套件有&#xff1a;msys&#xff0c;cygwin&#xff0c;mingw 优势&…

MySQL8的特性-MySQL8知识详解

MySQL是一个多用户、多线程的SQL数据库服务器。SQL&#xff08;结构化查询语言&#xff09;是世界上最流行和标准化的数据库语言。下面是MySQL的特性。 1、开源性&#xff1a;MySQL是一个开源的关系型数据库管理系统&#xff0c;可以免费使用和修改。 2、可靠性&#xff1a;M…

DOCKER的容器

1. 什么是Container&#xff08;容器&#xff09; 要有Container首先要有Image&#xff0c;也就是说Container是通过image创建的。 Container是在原先的Image之上新加的一层&#xff0c;称作Container layer&#xff0c;这一层是可读可写的&#xff08;Image是只读的&#xff0…

TOMCAT部署及优化(Tomcat配置文件参数优化,Java虚拟机(JVM)调优)

TOMCAT tomcat &#xff1a;是一个开放源代码的web应用服务器&#xff0c;基于java代码开发的。也可以理解为tomacat就是处理动态请求和基于java代码的页面开发。可以在html当中写入java代码&#xff0c;tomcat可以解析html页面当中的java&#xff0c;执行动态请求&#xff0c;…

Nvm安装与使用

【1】nvm下载地址 https://github.com/coreybutler/nvm-windows/releases 选择的是nvm-setup.exe 【2】安装nvm 打开cmd&#xff0c;输入命令nvm -v 查看nvm版本&#xff0c;出现如下界面说明成功 【3】nodejs 安装与管理 打开CMD命令&#xff0c;以管理员权限运行 1、…

如何维护自己的电脑

目录 1、关于电脑选择的建议 1.1、价格预算 1.2、明确需求 1.3、电脑配置 1.4、分辨率 1.5、续航能力 1.6、品牌选择 1.7、用户评测 1.8、各个电商平台对比 1.9、最后决策 2、我的选择 3、电脑保养 3.1 外部清洁 3.2 安装软件 3.3 优化操作系统 3.4 维护硬件设…

那些年的golang开发经验记录

goland 问题CreateProcess error216, 该版本的 %1 与你运行的 Windows 版本不兼容。请查看计算机的系统信息&#xff0c;然后联系软件发布者 Cannot run program "......" (in directory "D:\project\go\awesomeProject\src\test"): CreateProcess error2…