Java 动态规划 Leetcode 740. 删除并获得点数

这篇具有很好参考价值的文章主要介绍了Java 动态规划 Leetcode 740. 删除并获得点数。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目

Java 动态规划 Leetcode 740. 删除并获得点数,leetcode,java,动态规划

对于该题的题目分析,已经代码分析都一并写入到了代码注释中文章来源地址https://www.toymoban.com/news/detail-686365.html

代码

class Solution {
    public int deleteAndEarn(int[] nums) {
        //核心思路:
        //由于我们获得 nums[i] 的点数之后,就必须删除所有等于 nums[i] - 1 和 nums[i] + 1 的元素
        //假设我们现在要解决的数组为 1,2,3,4,5 当我们获得2的点数就不能获得 1,3 的点数,我们的选择就是 2,4 或者 1,3,5(即相邻的点数不能获取)
        //这样明显问题就简单了许多,所以我们要进行处理,将源数组转换为0,1,2,3...顺序排序的形式
        //我们可以创建一个辅助数组 arr ,让 arr 的下标表示源数组 nums[i] 的值, arr 的值表示源数组 nums[i] 值的总和
        //例如:对于nums=[2,2,3,3,3,4]
        //         arr=[0,0,4,9,4]
        //         下标:0,1,2,3,4
        //对于arr数组,我们就可以转换问题为相邻的点数不能获取求最大点数

        //由于 arr 数组的下标表示 nums 数组的值,而 nums 数组的值的最大值为10000(由题可知),所以 arr 数组的下标也要有10000
        int n=10001;
        int[] arr=new int[n];

        //初始化arr数组
        for(int x:nums){
            arr[x]+=x;
        }

        //创建dp表
        //对于arr数组中的点数我们可以选择要也可以选择不要
        //假设 f[i] 表示下标为i的点数我们必定要时所得的点数最大值, g[i] 表示下标为i的点数我们必定不要时所得的点数最大值
        // f[i] 由于下标为i的点数我们必定要,所以下标i-1的点数我们必定不要,那么到下标 i 我们能够获得的最大点数为f[i]=g[i-1]+arr[i]
        // g[i] 由于下标为i的点数我们必定不要,所以下标为 i-1 的点数我们可以选择要也可以选择不要,由于我们要求最大点数,所以我们应该选择点数较大的情况
        //g[i]=Math.max(f[i-1],g[i-1])
        //由于点数最大能达到10000,所以我们最大要判断10000这个点数是要还是不要,所以f数组和g数组都要开辟10001的大小
        int[]f=new int[n];
        int[]g=new int[n];

        //初始化
        //根据上面对f数组和g数组的分析,我们知道 i 的取值应该从1开始,所以我们需要知道f[0]和g[0]的值
        f[0]=arr[0];
        //g[0]=0;

        //填充dp数组
        for(int i=1;i<n;i++){
            f[i]=g[i-1]+arr[i];
            g[i]=Math.max(f[i-1],g[i-1]);
        }

        //返回值
        //当我们填充完f和g数组后,我们就知道了最后一个数选和不选的最大值,由于我们要的是最大点数,所以返回的应该是两个最大值中较大的一个
        return Math.max(f[n-1],g[n-1]);
    }
}

到了这里,关于Java 动态规划 Leetcode 740. 删除并获得点数的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • (动态规划) 剑指 Offer 60. n个骰子的点数 ——【Leetcode每日一题】

    难度:中等 把 n 个骰子扔在地上,所有骰子朝上一面的点数之和为 s 。输入 n ,打印出s的所有可能的值出现的概率。 你需要用一个浮点数数组返回答案,其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。 示例 1: 输入: 1 输出: [0.16667,0.16667,0.16667,

    2024年02月11日
    浏览(41)
  • 【LeetCode: 剑指 Offer 60. n个骰子的点数 | 数学+ 暴力递归=>记忆化搜索=>动态规划】

    🍎作者简介:硕风和炜,CSDN-Java领域新星创作者🏆,保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享💎💎💎 🍎座右铭:人生如棋,我愿为卒,行动虽慢,可谁曾见我后退一步?🎯🎯🎯 剑指 Offer 60. n个骰子的点

    2023年04月19日
    浏览(56)
  • LeetCode 1423. 可获得的最大点数(很经典的一道固定窗口的滑窗题)

    题目传送门 几张卡牌 排成一行,每张卡牌都有一个对应的点数。点数由整数数组 c a r d P o i n t s cardPoints c a r d P o in t s 给出。 每次行动,你可以从行的开头或者末尾拿一张卡牌,最终你必须正好拿 k k k 张卡牌。 你的点数就是你拿到手中的所有卡牌的点数之和。 给你一个整

    2024年01月16日
    浏览(41)
  • LeetCode | C++ 动态规划——583. 两个字符串的删除操作、72. 编辑距离

    583题目链接 做法一: 本题和1143.最长公共子序列基本相同,只要求出两个字符串的最长公共子序列长度即可,那么除了最长公共子序列之外的字符都是必须删除的,最后用两个字符串的总长度减去两个最长公共子序列的长度就是删除的最少步数。 做法二: 本题和115.不同的子

    2024年02月16日
    浏览(49)
  • leetcode877. 石子游戏(动态规划-java)

    来源:力扣(LeetCode) 链接:https://leetcode.cn/problems/stone-game Alice 和 Bob 用几堆石子在做游戏。一共有偶数堆石子,排成一行;每堆都有 正 整数颗石子,数目为 piles[i] 。 游戏以谁手中的石子最多来决出胜负。石子的 总数 是 奇数 ,所以没有平局。 Alice 和 Bob 轮流进行,Alic

    2024年02月10日
    浏览(56)
  • leetcode63. 不同路径 II(动态规划-java)

    来源:力扣(LeetCode) 链接:https://leetcode.cn/problems/unique-paths-ii 一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish”)。 现在考虑网格中有障碍物。

    2024年02月11日
    浏览(47)
  • leetcode300. 最长递增子序列(动态规划-java)

    来源:力扣(LeetCode) 链接:https://leetcode.cn/problems/longest-increasing-subsequence 给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。 子序列 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序

    2024年02月15日
    浏览(42)
  • leetcode1143. 最长公共子序列-动态规划(java)

    leetcode1143. 最长公共子序列 来源:力扣(LeetCode) 链接:https://leetcode.cn/problems/longest-common-subsequence 给定两个字符串 text1 和 text2,返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ,返回 0 。 一个字符串的 子序列 是指这样一个新的字符串: 它是由原字

    2024年01月19日
    浏览(43)
  • leetcode416. 分割等和子集(动态规划-java)

    来源:力扣(LeetCode) 链接:https://leetcode.cn/problems/partition-equal-subset-sum 给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。 示例 1: 输入:nums = [1,5,11,5] 输出:true 解释:数组可以分割成 [1, 5, 5] 和 [11] 。

    2024年02月11日
    浏览(36)
  • Java 动态规划 Leetcode 213. 打家劫舍 II

    代码展示:         该题其实是Java 动态规划 面试题 17.16. 按摩师的变种,增加了一个首尾是相邻的条件,而我们解决该题也要用到链接的这道题的思想,可以先去看一下上面这篇博客 此题可以采用动态规划的方法进行解决,根据解决动态规划题目的5大步骤进行逐步分析

    2024年02月13日
    浏览(39)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包