动态规划-删除并获得点数.md

title	date	categories	tags
动态规划：删除并获得点数	2022-07-28 07:10:36 -0700	数据结构与算法 动态规划	动态规划

注意

GitHub 的 Markdown 渲染功能不足，文章的完整渲染欢迎来我的 博客小站 查看~~

题目描述

思路与题解

;;;id1 思路 这题我承认我没有解出来，还是看了官方题解后才有思路的 🤣 怎么说呢，这道题如果你能转过弯，把它映射到我们前几道题所做的打家劫舍上，那这个题就很简单啦，关键就在于如何把这个题转换为打家劫舍~

再看一遍题干，你必须删除所有等于 nums[i] - 1 和 nums[i] + 1 的元素，意思不就是如果我们要获取 nums[i] 房屋的财产，那就不能获取 nums[i] 相邻两间房屋的财产了，所以我们的思路就是要把相同点数 i 累加起来，作为 nums[i] 的财产值，然后再用打家劫舍的滚动数组就可以啦

再次感叹一句，思路才是最重要和最宝贵的呀~ ;;;

;;;id1 我的题解

class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        int mv = 0;
        for (int v : nums) mv = max(v, mv);
        vector<int> sum(mv + 1);
        for (int v : nums) sum[v] += v;
        return rob(sum);
    }

private:
    int rob(vector<int>& nums) {
        int n = nums.size();
        int prev = 0, curr = nums[0];
        for (int i = 0; i < n; ++i) {
            int next = max(curr, prev + nums[i]);
            prev = curr;
            curr = next;
        }
        return curr;
    }
};

;;;