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

智能推荐

874计算机科学基础综合,2018年四川大学874计算机科学专业基础综合之计算机操作系统考研仿真模拟五套题...-程序员宅基地

文章浏览阅读1.1k次。一、选择题1． 串行接口是指( )。A. 接口与系统总线之间串行传送，接口与I/0设备之间串行传送B. 接口与系统总线之间串行传送，接口与1/0设备之间并行传送C. 接口与系统总线之间并行传送，接口与I/0设备之间串行传送D. 接口与系统总线之间并行传送，接口与I/0设备之间并行传送【答案】C2． 最容易造成很多小碎片的可变分区分配算法是( )。A. 首次适应算法B. 最佳适应算法..._874 计算机科学专业基础综合题型

XShell连接失败：Could not connect to '192.168.191.128' (port 22): Connection failed._could not connect to '192.168.17.128' (port 22): c-程序员宅基地

文章浏览阅读9.7k次，点赞5次，收藏15次。连接xshell失败，报错如下图，怎么解决呢。1、通过ps -e|grep ssh命令判断是否安装ssh服务2、如果只有客户端安装了，服务器没有安装，则需要安装ssh服务器，命令：apt-get install openssh-server3、安装成功之后，启动ssh服务，命令：/etc/init.d/ssh start4、通过ps -e|grep ssh命令再次判断是否正确启动..._could not connect to '192.168.17.128' (port 22): connection failed.

杰理之KeyPage【篇】_杰理 空白芯片 烧入key文件-程序员宅基地

文章浏览阅读209次。00000000_杰理 空白芯片 烧入key文件

一文读懂ChatGPT，满足你对chatGPT的好奇心_引发对chatgpt兴趣的表述-程序员宅基地

文章浏览阅读475次。2023年初，“ChatGPT”一词在社交媒体上引起了热议，人们纷纷探讨它的本质和对社会的影响。就连央视新闻也对此进行了报道。作为新传专业的前沿人士，我们当然不能忽视这一热点。本文将全面解析ChatGPT，打开“技术黑箱”，探讨它对新闻与传播领域的影响。_引发对chatgpt兴趣的表述

中文字符频率统计python_用Python数据分析方法进行汉字声调频率统计分析-程序员宅基地

文章浏览阅读259次。用Python数据分析方法进行汉字声调频率统计分析木合塔尔·沙地克;布合力齐姑丽·瓦斯力【期刊名称】《电脑知识与技术》【年(卷),期】2017(013)035【摘要】该文首先用Python程序,自动获取基本汉字字符集中的所有汉字,然后用汉字拼音转换工具pypinyin把所有汉字转换成拼音,最后根据所有汉字的拼音声调,统计并可视化拼音声调的占比.【总页数】2页(13-14)【关键词】数据分析;数据可..._汉字声调频率统计

linux输出信息调试信息重定向-程序员宅基地

文章浏览阅读64次。最近在做一个android系统移植的项目，所使用的开发板com1是调试串口，就是说会有uboot和kernel的调试信息打印在com1上（ttySAC0）。因为后期要使用ttySAC0作为上层应用通信串口，所以要把所有的调试信息都给去掉。参考网上的几篇文章，自己做了如下修改，终于把调试信息重定向到ttySAC1上了，在这做下记录。参考文章有：http://blog.csdn.net/longt..._嵌入式rootfs 输出重定向到/dev/console

随便推点

uniapp 引入iconfont图标库彩色symbol教程_uniapp symbol图标-程序员宅基地

文章浏览阅读1.2k次，点赞4次，收藏12次。1，先去iconfont登录，然后选择图标加入购物车 2，点击又上角车车添加进入项目我的项目中就会出现选择的图标 3，点击下载至本地，然后解压文件夹，然后切换到uniapp打开终端运行注：要保证自己电脑有安装node(没有安装node可以去官网下载Node.js 中文网)npm i -g iconfont-tools（mac用户失败的话在前面加个sudo，password就是自己的开机密码吧）4,终端切换到上面解压的文件夹里面，运行iconfont-tools 这些可以默认也可以自己命名（我是自己命名的_uniapp symbol图标

C、C++ 对于char*和char[]的理解_c++ char*-程序员宅基地

文章浏览阅读1.2w次，点赞25次，收藏192次。char*和char[]都是指针，指向第一个字符所在的地址，但char*是常量的指针，char[]是指针的常量_c++ char*

Sublime Text2 使用教程-程序员宅基地

文章浏览阅读930次。代码编辑器或者文本编辑器，对于程序员来说，就像剑与战士一样，谁都想拥有一把可以随心驾驭且锋利无比的宝剑，而每一位程序员，同样会去追求最适合自己的强大、灵活的编辑器，相信你和我一样，都不会例外。我用过的编辑器不少，真不少～ 但却没有哪款让我特别心仪的，直到我遇到了 Sublime Text 2 ！如果说“神器”是我能给予一款软件最高的评价，那么我很乐意为它封上这么一个称号。它小巧绿色且速度非

对10个整数进行按照从小到大的顺序排序用选择法和冒泡排序_对十个数进行大小排序java-程序员宅基地

文章浏览阅读4.1k次。一、选择法这是每一个数出来跟后面所有的进行比较。2.冒泡排序法，是两个相邻的进行对比。_对十个数进行大小排序java

物联网开发笔记——使用网络调试助手连接阿里云物联网平台（基于MQTT协议）_网络调试助手连接阿里云连不上-程序员宅基地

文章浏览阅读2.9k次。物联网开发笔记——使用网络调试助手连接阿里云物联网平台（基于MQTT协议）其实作者本意是使用4G模块来实现与阿里云物联网平台的连接过程，但是由于自己用的4G模块自身的限制，使得阿里云连接总是无法建立，已经联系客服返厂检修了，于是我在此使用网络调试助手来演示如何与阿里云物联网平台建立连接。一.准备工作1.MQTT协议说明文档（3.1.1版本）2.网络调试助手（可使用域名与服务器建立连接）PS：与阿里云建立连解释，最好使用域名来完成连接过程，而不是使用IP号。这里我跟阿里云的售后工程师咨询过，表示对应_网络调试助手连接阿里云连不上

＜＜＜零基础C++速成＞＞＞_无c语言基础c++期末速成-程序员宅基地

文章浏览阅读544次，点赞5次，收藏6次。运算符与表达式任何高级程序设计语言中，表达式都是最基本的组成部分，可以说C++中的大部分语句都是由表达式构成的。_无c语言基础c++期末速成

推荐文章

热门文章

相关标签