删除并获得点数

动态规划

这个和打家劫舍是一个思路，就是要想到如何转化成

首先，对问题的转化就需要我说的挖掘题目潜在条件

比如这里的潜在条件就是

• 同一个数字如果取走了就都要取走

这样就容易想到要转化一下数组，然后用打家劫舍的思路了

class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        vector<int> src_nums(1e4+10);
        int max_i = -1;
        for(auto i : nums) {
            max_i = max(max_i, i);
            src_nums[i] ++;
        }
 
        vector<int> dp(max_i+3);
        for(int i = 0; i < max_i+1; ++i) {
            dp[i+2] = max(dp[i+1], dp[i]+i*src_nums[i]);
        }
        return dp[max_i+2];
    }
};

顺带遍，这里进一步让我加深了 dp 数组的用法，这个所谓不需要初值的做法

考虑到 0 其实选不选无所谓，所以 dp 的长度正常来说是“房间”个数，现在全体递推 i+2，所以长度也加 2

然后其实你长度多了也无所谓，只要保证一直更新到最后一个，选不选都无所谓，最后返回值也得是 dp 的最后一个就行了

法二

可以想到，这里其实很多可能中间都是 0，然后不相邻的不相干，所以可以拆分成多个子问题做