力扣题解：740.删除并获得点数
文章目录
题干
给你一个整数数组 nums ，你可以对它进行一些操作。
每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素。
开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。
解题思路
输入示例：[3,7,10,5,2,4,8,9,9,4,9,2,6,4,6,5,4,7,6,10]
1.数据处理
每次取一个数 取一个数之后要删除掉i-1,i+1的数 也就是相邻的数 相同的数处理的逻辑是一样的 因此我们可以将同样的数合并变成以下数据格式：
{3:3,7:14}示例数据经过处理之后变成了以下数据格式 v:v的价值
const inputData =[3,7,10,5,2,4,8,9,9,4,9,2,6,4,6,5,4,7,6,10];const map ={3:3,7:14,10:20,5:10,2:4,4:16,8:8,9:27,6:18}在处理的过程中记录一下数组中的最大值 在后面需要用到
2.状态转移
看到题目上有删除的需求 第一时间想到的就是取到一个值之后手动删除i-1,i+1对应的值 其实不用这样 可以用状态转移公式来完成取值
所谓状态转移公式就是用来描述当前状态的最优结果，如何由之前的状态推导出来的公式。
比如最简单的爬楼梯问题 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
那我们就可以想到 假如总共5层楼梯 推算过程如下
- 到第一层楼梯只能的次数只能是1
- 到第二层楼梯就有了两个选择
- 跳两次一层
- 跳一次两层
显然跳一次两层次数最少
- 到第三层此时我们就不能手动算了，我们可以推算出来，到第一层楼梯的次数恒定为1，到第二层楼梯的次数可以是1也可以是2，那到第三层楼梯的的方法次数就是到第一层的方法次数+到第二层的方法次数 显然到第三层楼梯的方法次数只能是加上到他前面楼梯的方法次数，这是肯定的 变成公式就是：
到当前楼梯的方法次数 = 到前楼梯前面第一层的方法次数 + 到前楼梯前面第二层的方法次数
伪代码：
dp[n] = dp[n - 1] + dp[n - 2]
继续推算 - 到第一层的方法次数：1
- 到第二层的方法次数：1
- 到第三层最方法次数：2
- 到第四层的方法次数：2 + 1 = 3
- 到第五层的方法次数：3 + 2 = 5
- 到顶层的方法次数：5 + 3 = 8
所以当n=5时 最多有8种方法到达顶层
这里通过推算得出来的公式就是状态转移公式通过这个公式我们可以很轻松的算出到每个层的最多有多少个不同的方法。
3.解题思路
回到当前的题目 我们已经得到了每个值对应的价值 此时我们就要借鉴另外一个题里面的思想了打家劫舍这个题目的需求跟现在我们要处理的问题是差不多的，需要得出最大值。
在打家劫舍题目里面解题思路是我们先拿到一个 拿下一个的时候判断是当前这个加上我们上上个拿到的值大 还是上一个值大 因为不能拿相邻的所以我们拿了当前的 就要舍弃拿的上一个 为什么要加上 上上个 因为我们要算能拿到的最大值。根据思路 我们推算出状态转移公式：
dp[i] = Math.max(dp[i - 2] + v,dp[i-1]) 当前的值 等于当前拿到的值加上 上上个的值或者上一个值 两者只能取一个。
这个题目也是一样的 我们需要得到相加出来最大的值 当前的值等于当前拿的值加上 上上个值或者上个值 拿取一个值后需要去除i-1,i+1对应的值 实际上在取值的时候就处理了
示例数据：
const map ={3:3,7:14,10:20,5:10,2:4,4:16,8:8,9:27,6:18}const dp =[] dp[0]=0 dp[1]= map.get(1)||0实际代码写的时候会排序 所以这里的数据可以看成是已升序排序后的
比如我们拿2的时候就会判断当前值4加上 上上个值也就是索引0为0的值和上个值谁大 结果是4更大 所以dp[2] = 3 这个值就代表着前两个的最大值加起来是3 下一轮的取3的时候就是当前值3加上 上上个值0或者上个值3 结果是4大取了4，当下一轮取4的时候 值是16 加上i-2的值4等于20 大于i-1的值4 所以取4
现在的dp数组为：
dp[0]=0 dp[1]=0 dp[2]=4 dp[3]=4 dp[4]=16当公式一直执行下去便得到了最终结果。
这里还有一个问题就是题目说了取了一个值之后就需要去掉i-1和i+1对应的值 但我们这里好像没有处理 只处理了不能取i-1的值
我们先看公式
db[i] = Math.max(dp[i - 2] + v,dp[i-1]) 假如3的值是6 我们取了2之后 接着是取3 6比4大 取了3 发现并没有去除2+1的值 但是我们仔细想想：我们3的值是哪来的 是通过dp[i - 2] + v得来的 已经跳过了i-1 也就是2的值 这里公式已经跳过了选择2 所以下一轮取了3并不是取了相邻的 只是取了公式下的最优解。
4.题解
/** * @param {number[]} nums * @return {number} */vardeleteAndEarn=function(nums){if(nums.length ===1)return nums[0]let m =newMap()let maxVal =0for(let i =0; i < nums.length; i++){ m.set(nums[i],(m.get(nums[i])||0)+ nums[i]);if(nums[i]> maxVal) maxVal = nums[i];}const dp =[] dp[0]=0 dp[1]= m.get(1)||0;for(let i =2; i <= maxVal; i++){const gain = m.get(i)||0; dp[i]= Math.max(gain + dp[i -2],dp[i -1])}return dp[maxVal]
