leetcode刷题(2022.05.15)

难度：中等。

给一个数组，在数组中获得满足要求的最大分数。
要求：对于取得x的分数，x-1和x+1的分数不能获得。
其实跟之前那个差不多，做了一次转换而已

统计每个数字出现的数量，然后找当前位置的最大分数。
对于第i个位置存在: d p [ i ] = m a x ( n u m [ i ] ∗ i + d p [ i − 2 ] , d p [ i − 1 ] ) dp[i]=max(num[i]*i+dp[i-2],dp[i-1]) dp[i]=max(num[i]∗i+dp[i−2],dp[i−1])
其中num[i]里面记录的是i出现的次数。因为数量级不大，直接开了num[10002]用来存，然后遍历一个最大的ans。

class Solution {
public:
    int dp[10002]={0};
    int num[10002]={0};
    int deleteAndEarn(vector& nums) {
        int n=nums.size();
        if(n==1)return nums[0];
        for(int i=0;i
            ++num[nums[i]];
        }
       dp[1]=dp[0]>num[1]?dp[0]:num[1];
       int ans=-1;
       for(int i=2;i<10002;i++)
       {
           dp[i]=num[i]*i+dp[i-2]>dp[i-1]?num[i]*i+dp[i-2]:dp[i-1];
           ans=max(ans,dp[i]);
       }
       return ans;
    }
};

时间复杂度O(1^4+N)
空间复杂度O(2*10^4)

优化方法还有很多，比如在dp和num数组中有很多是浪费的可以不去记录等等。