LeetCode740. 删除并获得点数(java/c++动态规划)
2021/5/5 12:27:06
本文主要是介绍LeetCode740. 删除并获得点数(java/c++动态规划),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
740. 删除并获得点数(动态规划)
链接:https://leetcode-cn.com/problems/delete-and-earn/solution/javadong-tai-gui-hua-100da-jia-jie-she-b-n5o7/
解题思路
没做过打家劫舍的可以先做做198.打家劫舍
创建一个新数组count,对nums[i]计数,将这个题转换为打家劫舍的思路
推导公式为 dp[i] = Math.max(dp[i-1], dp[i-2]+count[i]*i);
java代码:
class Solution { public int deleteAndEarn(int[] nums) { int n = nums.length; if(n <= 1 ) return nums[0]; int max = nums[0]; for(int i : nums) { max = Math.max(max, i); } int[] count = new int[max+1]; for(int i : nums) { count[i]++; } int[] dp = new int[max+1]; dp[1] = count[1]*1; dp[2] = Math.max(dp[1], count[2]*2); for(int i = 3; i <= max; i++) { dp[i] = Math.max(dp[i-1], dp[i-2]+count[i]*i); } return dp[max]; } }
c++代码:
class Solution { public: int deleteAndEarn(vector<int>& nums) { int n = nums.size(); if( n == 1) return nums[0]; int maxnum = nums[0]; for(int i : nums) { maxnum = max(i,maxnum); } vector<int> count(maxnum+1),dp(maxnum+1); for(int i : nums) { count[i]++; } dp[1] = count[1]; for(int i = 2; i <= maxnum; i++) { dp[i] = max(dp[i-1],dp[i-2] + count[i]*i); } return dp[maxnum]; } };
这篇关于LeetCode740. 删除并获得点数(java/c++动态规划)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-24Java中定时任务实现方式及源码剖析
- 2024-11-24Java中定时任务实现方式及源码剖析
- 2024-11-24鸿蒙原生开发手记:03-元服务开发全流程(开发元服务,只需要看这一篇文章)
- 2024-11-24细说敏捷:敏捷四会之每日站会
- 2024-11-23Springboot应用的多环境打包入门
- 2024-11-23Springboot应用的生产发布入门教程
- 2024-11-23Python编程入门指南
- 2024-11-23Java创业入门:从零开始的编程之旅
- 2024-11-23Java创业入门:新手必读的Java编程与创业指南
- 2024-11-23Java对接阿里云智能语音服务入门详解