题目描述给你一个整数数组numsnumsnums你可以对它进行一些操作。每次操作中选择任意一个nums[i]nums[i]nums[i]删除它并获得nums[i]nums[i]nums[i]的点数。之后你必须删除 所有 等于nums[i]−1nums[i] - 1nums[i]−1和nums[i]1nums[i] 1nums[i]1的元素。开始你拥有000个点数。返回你能通过这些操作获得的最大点数。示例 1输入nums [3,4,2]输出6解释删除 4 获得 4 个点数因此 3 也被删除。nums [2]之后删除 2 获得 2 个点数。nums []总共获得 6 个点数。示例 2输入nums [2,2,3,3,3,4]输出9解释删除 3 获得 3 个点数。所有的 2 和 4 也被删除。nums [3,3]之后再次删除 3 获得 3 个点数。nums [3]再次删除 3 获得 3 个点数。nums []总共获得 9 个点数算法思想根据题目描述如果在numsnumsnums中选择了nums[i]nums[i]nums[i]那nums[i]−1nums[i] - 1nums[i]−1和nums[i]1nums[i] 1nums[i]1就不能选。假设nums[1,2,3,4,5]nums [1, 2, 3, 4, 5]nums[1,2,3,4,5]刚开始选择111就无法选择相邻的222接下来选择333就无法选择相邻的444。这和打家劫舍 I是类似的。但是假设nums[1,1,2,2,4,4,5,7]nums [1, 1, 2, 2, 4, 4, 5, 7]nums[1,1,2,2,4,4,5,7]由于数字不连续选了222以后相邻的数字444还是可以选的因此可以创建一个数组arrarrarrarr[nums[i]]arr[nums[i]]arr[nums[i]]保存的是numsnumsnums中所有nums[i]nums[i]nums[i]之和代入上面的numsnumsnums中就后arrarrarr的样子就是由于下标是连续的所以能够转化为打家劫舍 I具体做法为先求出numsnumsnums中相同nums[i]nums[i]nums[i]的和填入arr[nums[i]]arr[nums[i]]arr[nums[i]]然后做一次打家劫舍 I创建两个数组fff和ggg确定状态表示f[i]f[i]f[i]表示选择了arr[i]arr[i]arr[i]之后的最大点数g[i]g[i]g[i]表示没选择arr[i]arr[i]arr[i]时的最大点数确定状态转移方程f[i]f[i]f[i]要选择arr[i]arr[i]arr[i]所以arr[i−1]arr[i-1]arr[i−1]不选f[i]f[i]f[i]就等于不选arr[i−1]arr[i-1]arr[i−1]时的最大点数加上arr[i]arr[i]arr[i]也就是f[i]g[i−1]arr[i]f[i] g[i - 1] arr[i]f[i]g[i−1]arr[i]。g[i]g[i]g[i]不选arr[i]arr[i]arr[i]所以arr[i−1]arr[i-1]arr[i−1]可选不选选择了arr[i−1]arr[i-1]arr[i−1]g[i]g[i]g[i]就等于选了arr[i−1]arr[i-1]arr[i−1]时的最大点数就是f[i−1]f[i-1]f[i−1]。不选择arr[i−1]arr[i-1]arr[i−1]g[i]g[i]g[i]就等于不选arr[i−1]arr[i-1]arr[i−1]时的最大点数就是g[i−1]g[i-1]g[i−1]g[i]g[i−1]g[i] g[i-1]g[i]g[i−1]。所以g[i]max(f[i−1],g[i−1])g[i] max(f[i-1], g[i-1])g[i]max(f[i−1],g[i−1])初始化根据状态转移方程000下标填的时候会越界所以初始化f[0]f[0]f[0]和g[0]g[0]g[0]根据状态表示f[0]arr[0]f[0] arr[0]f[0]arr[0]g[0]0g[0] 0g[0]0填表顺序从左向右两个一起填返回值要选到最后一个位置最后一个位置可选可不选所以是max(f[n−1],g[n−1])max(f[n - 1], g[n - 1])max(f[n−1],g[n−1])代码classSolution{public:intdeleteAndEarn(vectorintnums){intnnums.size();intm*max_element(nums.begin(),nums.end());vectorintarr(m1,0);for(inti0;in;i)arr[nums[i]]nums[i];vectorintf(m1,0);vectorintg(m1,0);f[0]arr[0];g[0]0;for(inti1;im;i){f[i]g[i-1]arr[i];g[i]max(f[i-1],g[i-1]);}returnmax(f[m],g[m]);}};