[C++&Rust]LeetCode No.740 删除并获得点数(每日一题)
2021/5/5 14:25:45
本文主要是介绍[C++&Rust]LeetCode No.740 删除并获得点数(每日一题),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
原帖地址:http://blog.leanote.com/post/dawnmagnet/b50143d626a8
题目
思路分析
这个题一看还是一个dp,本月是dp月实锤了???
还是那句老话,但凡是看起来模拟能做的都往dp的方向考虑考虑。
在本题中,可以看出,选了nums[i]就不能选加一和减一了,这是最关键的约束条件,我们的dp也应该由此展开。
所以我们统计一下每个数字出现的次数(存放在cal中)。dp的时候自然就是对nums[i]从前向后dp。一共取值范围是10000,也不大。
dp的时候我们有个优势,因为对于dp来说,向后的约束条件是可以直接忽略的,什么叫做向后的约束条件呢,就是nums[i] + 1的元素对我们来说还没遍历到,所以可以直接忽略该条件,只考虑不能取nums[i] - 1即可。
那么这个题目就变成了,10000个数字,最少隔着一个取,问和的最大值。那么这个题目已经变成了一个非常非常简单的入门级动态规划问题。
就直接dp[i] = max(dp[i-1], cal[i]*i+在i-1之前dp能取到的最大值),为什么要乘最大值不取i-1呢,因为题目的条件呀!
直接就出答案了。
在i-1之前dp能取到的最大值也可以通过循环来计算,也非常简单,在i循环完成之后,再把dp[i-1]和改值取个最大值即可。
这个也称为延迟最大值,计算也非常方便。而且这个res本身也可以作为返回值,只需要和最后一项dp比较一下即可
Rust代码
impl Solution { pub fn delete_and_earn(nums: Vec<i32>) -> i32 { let mut dp = [0; 10001]; for num in nums { dp[num as usize] += num; } let mut res = 0; for i in 1..=10000 { dp[i] = dp[i - 1].max(dp[i] + res); res = res.max(dp[i - 1]); } res.max(dp[10000]) } }
C++代码
class Solution { public: int deleteAndEarn(vector<int>& nums) { int dp[10001] = {0}; for (auto & num : nums) dp[num] += num; int res = 0; for (int i = 1; i <= 10000; ++i) { dp[i] = max(dp[i - 1], dp[i] + res); res = max(res, dp[i - 1]); } return max(res, dp[10000]); } };
这篇关于[C++&Rust]LeetCode No.740 删除并获得点数(每日一题)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26小白家庭 nas 搭建方案-icode9专业技术文章分享
- 2024-06-23AI大模型企业应用实战(14)-langchain的Embedding
- 2024-06-23AI大模型企业应用实战(15)-langchain核心组件
- 2024-06-23AI大模型企业应用实战(16)-langchain核心组件
- 2024-06-23AI 大模型企业应用实战(06)-初识LangChain
- 2024-06-19EntBot.ai: AI Website Chatbot for Product Guides and Development Doc
- 2024-06-17zero-shot-learning-definition-examples-comparison
- 2024-06-06Package Easy(基于 NSIS 的打包exe安装包工具)使用方法-icode9专业技术文章分享
- 2024-06-06基于 casdoor 的 ELK 开源登录认证解决方案: elk-auth-casdoor-icode9专业技术文章分享
- 2024-05-29Elasticsearch慢查询日志配置