力扣 -- 740. 删除并获得点数

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

力扣 -- 740. 删除并获得点数,力扣经典面试题,力扣动态规划,leetcode,算法,职场和发展,c++,数据结构,动态规划

题目链接:740. 删除并获得点数 - 力扣(LeetCode) 

下面是用动态规划的思想解决这道题的过程,相信各位小伙伴都能看懂并且掌握这道经典的动规题目滴。

力扣 -- 740. 删除并获得点数,力扣经典面试题,力扣动态规划,leetcode,算法,职场和发展,c++,数据结构,动态规划

参考代码:


class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        //根据题意,nums[i]的值满足1<=nums[i]<=10000
        //所以哈希表映射可以开一个10001个空间的大小
        const int n=10001;
        int arr[n]={0};
        //把大小等于nums[i]的值的综合映射到arr数组中下标为nums[i]的位置上去
        for(const auto& x:nums)
        {
            arr[x]+=x;
        }
        //以下就变成了对arr数组做打家劫舍问题
        vector<int> f(n);
        vector<int> g(n);
        //初始化
        f[0]=arr[0];
        g[0]=0;
        //填表,因为arr数组的每一个位置都有可能有值,所以要遍历整个arr数组
        for(int i=1;i<n;i++)
        {
            f[i]=g[i-1]+arr[i];
            g[i]=max(f[i-1],g[i-1]);
        }
        return max(f[n-1],g[n-1]);
    }
};

 以上就是用动态规划的思想分析这道题目的整个过程啦,你学会了吗?如果以上题解对你有所帮助,那么就点亮一下小心心,点点关注呗,后期还会持续更新动态规划的经典题目哦,我们下期见!!!!! !!!!文章来源地址https://www.toymoban.com/news/detail-525447.html

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

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

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

相关文章

  • 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日
    浏览(43)
  • 一维动态规划经典力扣题目(一)

    目录 题一:斐波那契数列 题目二:最低票价 题三:解码方法 递归方法是2的n次方的时间复杂度。 递归代码: 带有缓存的递归,会使时间复杂度得到大幅度优化。 时间复杂度为O(n)。 缓存即记录中间值         优化的方法:         代码:         代码:

    2024年02月21日
    浏览(41)
  • 力扣思维题/经典面试题——下一个排序

    https://leetcode.cn/problems/next-permutation/description/ 字节面试题,非常经典的逻辑思维题 1、找到第一个下降点,说明这个点可以 变得稍微大一点 以至于让整个排列变得更加大 为什么,仔细想想,后面都是倒序了怎么都不可能变得更加大了 2、下降点变成多大呢? 变成后面比它大的

    2024年02月04日
    浏览(41)
  • LeetCode力扣 面试经典150题 详细题解 (1~5) 持续更新中

    目录 1.合并两个有序数组 2.移动元素  3.删除有序数组中的重复项  4.删除排序数组中的重复项 II 5.多数元素 暂时更新到这里,博主会持续更新的 题目(难度:简单): 给你两个按 非递减顺序 排列的整数数组  nums1   和  nums2 ,另有两个整数  m  和  n  ,分别表示  nu

    2024年02月19日
    浏览(42)
  • 力扣动态规划专题(六)编辑距离与回文问题 步骤及C++实现

    步骤 确定dp数组以及下标的含义 dp[i][j] 表示以下标i-1为结尾的字符串s,和以下标j-1为结尾的字符串t,相同子序列的长度。判断s是否为t的子序列。即t的长度是大于等于s的 确定递推公式 和题1143一样,不同的是只有t可以删除元素,1143题两个字符串都可以删除元素 t中找到一

    2024年02月11日
    浏览(33)
  • 【面试经典150 | 动态规划】零钱兑换

    【动态规划】【数组】 322. 零钱兑换 定义状态 dp[i] 表示凑成总金额的最少硬币个数。 状态转移 从小到大枚举要凑成的金额 i ,如果当前的金额可以使用面额数组中的某个面额 coin 凑成总金额的一部分,则可以更新 d p [ i ] = m i n ( d p [ i ] , d p [ i − c o i n ] + 1 ) dp[i] = min(dp[i

    2024年04月16日
    浏览(71)
  • 递归究竟是什么?如何快速编写正确的递归代码? —— 力扣经典面试题详解

    下面是来自百度百科对递归算法的定义:  递归是一种算法设计技术,它允许一个函数在其定义或说明中有直接或间接调用自身的方法。  递归在数学和计算机科学中有着广泛的应用,它通过将复杂问题分解为规模较小、形式相同的子问题来求解。递归的基本原理包括:每

    2024年04月09日
    浏览(51)
  • 【面试经典150 | 动态规划】交错字符串

    本专栏专注于分析与讲解【面试经典150】算法,两到三天更新一篇文章,欢迎催更…… 专栏内容以分析题目为主,并附带一些对于本题涉及到的数据结构等内容进行回顾与总结,文章结构大致如下,部分内容会有增删: Tag:介绍本题牵涉到的知识点、数据结构; 题目来源:

    2024年04月15日
    浏览(68)
  • 面试经典150题——删除有序数组中的重复项

    题目来源 力扣每日一题;题序:26 我的题解 方法一 双指针 使用两个指针分别指向相同元素的左右边界,再利用一个count记录最终需要的数组长度。 时间复杂度 :O(n) 空间复杂度 :O(1) 有任何问题,欢迎评论区交流,欢迎评论区提供其它解题思路(代码),也可以点个赞支持

    2024年04月14日
    浏览(59)
  • 算法学习——LeetCode力扣动态规划篇3(494. 目标和、474. 一和零、518. 零钱兑换 II)

    494. 目标和 - 力扣(LeetCode) 描述 给你一个非负整数数组 nums 和一个整数 target 。 向数组中的每个整数前添加 ‘+’ 或 ‘-’ ,然后串联起所有整数,可以构造一个 表达式 : 例如,nums = [2, 1] ,可以在 2 之前添加 ‘+’ ,在 1 之前添加 ‘-’ ,然后串联起来得到表达式 “

    2024年04月14日
    浏览(56)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包