leetcode 486. 预测赢家 (动态规划）java_486 预测赢家(动态规划)-程序员宅基地

技术标签： LeetCode  

1.问题

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

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

在这里插入图片描述
力扣（LeetCode）
原题链接;

2.方案

把玩家1，玩家2同时选完一轮后，玩家1与玩家2的分数差看做一个子问题；用dp[i][j]表示为数组的首索引为i,尾索引为j时，玩家1与玩家2最终的分数差。
循环方程： d p [ i ] [ j ] = m a x ( n u m s [ i ] − d p [ i + 1 ] [ j ] , n u m s [ j ] − d p [ i ] [ j − 1 ] ) dp[i][j] = max(nums[i] - dp[i+1][j], nums[j] - dp[i][j-1]) dp[i][j]=max(nums[i]−dp[i+1][j],nums[j]−dp[i][j−1]);
然后，基础解为 i==j 时， dp[i][j] = nums[i]. 代码实现可以用递归，或者使用循环求解。

基于递归：

class Solution {
    public boolean PredictTheWinner(int[] nums) {
      int[][] dp = new int[nums.length][nums.length];
      int res = getDp(nums, 0, nums.length-1, dp);
      if(res < 0) return false;
      return true;
    }
    public int getDp(int[] nums, int i, int j, int[][] dp){
      if(i == j) return nums[i];
      if(i> j) return 0;
      dp[i][j] = Math.max(nums[i] - getDp(nums, i+1, j, dp), nums[j] - getDp(nums, i, j-1, dp));
      
      return dp[i][j];
    }
}

基于循环：

// improve
class Solution {
    public boolean PredictTheWinner(int[] nums) {
        int n = nums.length;
        int[][] dp = new int[n][n];
        //初始化
        for (int i = 0; i < n; i++) {
            dp[i][i] = nums[i];
        }
        //DP
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                dp[i][j] = Math.max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1]);
            }
        }
        return dp[0][n - 1] >= 0;
    }
}
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/rosefun96/article/details/100025719

智能推荐

Qt on Android：图文详解Hello World全过程_qt kids-程序员宅基地

文章浏览阅读1.6k次。这是系列文章中的一篇，阅读本文前请先阅读《Windows下Qt 5.2 for Android开发入门》，以便确保开发环境和作者一致。部分文章被转发/转载却没有注明出处，特此声明：版权所有 foruok ，如需转载敬请注明出处(http://blog.csdn.net/foruok)。我将从实践出发，带领大家一步一步完成在 Android 上的第一个 Qt 应用： Hello Qt_qt kids

RIP、OSPF、BGP协议之间的区别_rip,ospf,bgp三个协议的区别-程序员宅基地

文章浏览阅读1.5k次，点赞3次，收藏11次。③只有当链路状态发生变化时，路由器才用洪泛法向所有路由器发送此信息，并且更新过程收敛的快，不会出现RIP“坏消息传得慢”的问题。②发送的信息是与本路由器相邻的所有路由器的链路状态，但这只是路由器所知道的部分信息。③网络出现故障时，会出现慢收敛现象，俗称“坏消息传得慢”，使更新过程的收敛时间长。②路由器之间交换的是路由器中的完整路由表，因此网络规模越大，开销也越大。：BGP是不同自治系统的路由器之间交换路由信息的协议，是一种外部网关协议。②路由器交换的信息是当前路由器所知道的全部信息，即。_rip,ospf,bgp三个协议的区别

uni-app运行到微信小程序报错[ pages/index/index.json 文件内容错误] pages/index/index.json: [“usingComponents“][“u-nav-程序员宅基地

文章浏览阅读6.1k次。uni-app运行到微信小程序时报错：“[ pages/index/index.json 文件内容错误] pages/index/index.json: [“usingComponents”][“u-navbar”] 未找到”这是由于引用了第三方UI库，比如uview，pages.json配置easycom规则(按需引入)，使用了npm安装方式，但微信开发者工具没有构建npm，可以改下下载方式// pages.json{ "easycom": { // 下载安装的方式需要前面_[ pages/index/index.json 文件内容错误] pages/index/index.json: ["usingcompon

五分钟了解物联网SIM卡——这个文章刷新了我对sim卡的认识_中移物联nb-iot模块 不认识sim卡-程序员宅基地

文章浏览阅读6.7k次，点赞32次，收藏108次。嵌入式软件自留地 今天编者荐语：五分钟了解物联网SIM卡——这个文章刷新了我对sim卡的认识，不熟悉的可以看看~~以下文章来源于华为云IoT ，作者我是卤蛋这个文章来自网络，看了觉得不错，因此特意整理转载下。是华为iot小助手分享的，都知道华为在物联网领域是国内老大的地位，分享的文章还是比较有价值的。【摘要】SIM卡是移动通信中不可或缺的组成部分，在物联网解决方案中，设备移动上网也需要使用SIM卡。那么，SIM卡是什么？SIM卡有几种？各种SIM卡有什么区别？本文将为您答疑.._中移物联nb-iot模块 不认识sim卡

js获取当前Unix时间戳_js unix时间戳-程序员宅基地

文章浏览阅读1.1w次。JavaScript 获取当前时间戳：第一种方法：var timestamp = Date.parse(new Date());第二种方法:var timestamp=new Date().getTime()；第三种方法：var timestamp = (new Date()).valueOf();第一种：获取的时间戳是把毫秒改成000显示，_js unix时间戳

Chrome浏览器各种文件的存放路径汇总_chrome 浏览器 网页 pdf 文件 保存在哪里-程序员宅基地

文章浏览阅读5.1k次。2021-03-18首次编辑Profile文件什么是Profile文件？chrome://version可以查看 个人资料路径书签文件的存贮路径/Users/username/Library/Application Support/Google/Chrome/Default/Bookmarks扩展插件存放位置/Users/username/Library/Application Support/Google/Chrome/Default/Extensions..._chrome 浏览器 网页 pdf 文件 保存在哪里

随便推点

python抛出异常会终止程序吗_Python学习笔记之类型判断，异常处理，终止程序操作小结...-程序员宅基地

文章浏览阅读4.9k次。python学习笔记 类型判断，异常处理，终止程序，实例代码：#idle中按F5可以运行代码#引入外部模块 import xxx#random模块，randint(开始数，结束数) 产生整数随机数import randomimport sysimport ossecret = random.randint(1,10)temp = input("请输入一个数字\n")#print(type(temp..._程序抛出异常不一定终止程序

引用Dll失败-程序员宅基地

文章浏览阅读583次。C#中添加引用Dll文件必须先注册！！注册方法：regsvr32 *.dll (*代表Dll文件名称)！！_引用dll失败

vscode-python的debug 教学(最全)_vscode python debug_python vs debug-程序员宅基地

文章浏览阅读685次，点赞14次，收藏25次。Visual Studio Code 的主要功能之一是其强大的调试支持。VS Code 的内置调试器有助于加速编辑、编译和调试循环。在插件库内搜索python Debugger，安装插件（1）创建debug_learning.py测试文件（2）设置断点（2）启动debug模式（3）debug的各个按钮的介绍以下文档基于内置的 Node.js 调试器，但大多数概念和功能也适用于其他调试器。在阅读有关调试的信息之前，首先创建一个示例Node.js应用程序会很有帮助。您可以按照Node.js演练安_python vs debug

[附源码]计算机毕业设计Python+uniapp家校通微信小程序rjeuh(程序+lw+远程部署)_家校互通小程序开源-程序员宅基地

文章浏览阅读112次。Python3.7.7+Django+Mysql5.7+pip list+HBuilderX（Vscode也行）+uni+Vue+Pychram社区版。[附源码]计算机毕业设计Python+uniapp家校通微信小程序rjeuh(程序+lw+远程部署)2. 前端：uni+css+javascript+jQuery+easyUI+highcharts。Django + uni小程序 +Python+Mysql 等等组成，B/S模式等等。该项目含有源码、文档、程序、数据库、配套开发软件、软件安装教程。_家校互通小程序开源

快手 sig(sign)签名算法 java版_java获取快手视频评论数-程序员宅基地

文章浏览阅读1.5w次，点赞5次，收藏31次。需求：想要获取快手短视频app的用户粉丝数声明：本博文只是作为研究学习用途，请不要用于非法、商业用途。写个帖子不容易，转载请说明出处，谢谢首先需要用Fidder抓包工具找到接口地址重点来了，快手所有的接口基本都用到了一个参数sig(数据签名)声明：本博文只是作为研究学习用途，请不要用于非法、商业用途。写个帖子不容易，转载请说明出处，谢谢首先需要用Fidder抓包工具找到接口地址这个过程省略..._java获取快手视频评论数

【100天精通python】Day1：python入门_初识python，搭建python环境，运行第一个python小程序_python一百天-程序员宅基地

文章浏览阅读3.3k次，点赞22次，收藏85次。Python是一种高级、通用、解释型编程语言。它具有简单易学的语法和强大的功能，适用于多种应用领域，包括Web开发、数据分析、人工智能和科学计算等。Python拥有庞大的社区支持，且拥有丰富的第三方库和工具，使得开发变得更加高效和便捷。python 语言不仅可以应用到网络编程、游戏开发等领域，还可以在图形图像处理、智能机器人、爬取数据、自动化运维等多方面发挥特长，为开发者提供简约、优雅的编程体验。_python一百天

推荐文章

热门文章

相关标签