740. Delete and Earn

想法會卡住, 在看到的當下完全沒有頭緒

dp的題目就難在怎麼看破

這邊看到有人提到可以用搶劫dp題來做, 看了就懂了, 搶劫的問題是不能同時搶兩間鄰居, 這這邊有點像, 我們可以把他列成1–10001的array, 然後再決定每一個element是否要取, 如果不要, 就直接繼承上一個的結果, 如果要, 就是要拿上上個的結果, 再加上這次獲得的分數

class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        vector<int> arr(10001, 0);
        int maxNum = INT_MIN;
        for(int i = 0; i < nums.size();i++){
            arr[nums[i]]++;
            maxNum = max(nums[i], maxNum);
        }
        vector<int> dp(10001, 0);
        dp[0] = arr[0];
        dp[1] = arr[1];
        int res = dp[1];
        for(int i = 2 ; i < maxNum + 1;i++){
            dp[i] = max(dp[i - 2] + arr[i] * i, dp[i - 1]);
            res = max(res, dp[i]);
        }
        return res;
}
};