黄骗免费网站,最好的网站设计,wordpress游戏代练主题,网站动图怎么做这道题和打家劫舍得思路很像。
思路#xff1a;首先我们看到题目的意思#xff0c;就是说我们如果选择了一个数#xff0c;那么它相邻的数就会不得选入#xff0c;也就是删除。这就是上一个题那个相邻的家不能偷的问题呗#xff01;
我们从那个地方转换一下#xff0c;…这道题和打家劫舍得思路很像。
思路首先我们看到题目的意思就是说我们如果选择了一个数那么它相邻的数就会不得选入也就是删除。这就是上一个题那个相邻的家不能偷的问题呗
我们从那个地方转换一下也就是说我们现在选择的数就是用来偷窃财产的房间号只不过这个时候房间号相同的个数增加了不是一个了所以我们需要计数。由于给出的样例里面数都是相邻的所以我们需要排个序因为顺序可能是不一样的这样不会影响结果。
接下来就按照上一道题的思路写dp的转移方程就行。
注意首先就是数组的大小开多大的问题就是按照数据范围开就行。然后注意尽量不要用nums[i]你可能会漏了判断n的个数是多少导致出现数组越界的错误。所以我们就直接用循环中的i代替就行因为反正排完序之后顺序就是一样的数字也是相邻的所以我们直接用循环变量代替就行了。
上代码
class Solution {
public:int deleteAndEarn(vectorint nums) {sort(nums.begin(),nums.end());int maxsnums.back();vectorintdp(10001,0);vectorintcount(10001,0);for(int val:nums)count[val];dp[1]count[1];for(int i2;imaxs;i){dp[i]max(dp[i-1],dp[i-2]i*count[i]);}return dp[maxs];}
};
