当前位置：首页 > ops >正文

动态规划-740.删除并获取节点-力扣(LeetCode)

ops 2025/8/4 18:09:55

一、题目解析

根据这个示例1，选择删除4并获得4，那么3和5都会被删除掉且不会被获取，选择删除2并获得2，那么1和3都会被删除且不会获得，这样一看或许对这道题感觉无从下手，但我换一种表达形式你能看出些名堂来。我们将示例1重新按升序排好序，得到2,3,4，这时在一看之前的规则，是不是可以将其转化为不能取相邻的数据，这和我们的打家劫舍问题是不是相同的？我们通过对条件的理解将一道全新的题转化为我们熟悉的题。对于打家劫舍不熟悉的读者可以先移步观看我之前的博客，链接：动态规划-LCR 089.打家劫舍-力扣(LeetCode)-CSDN博客

二、算法原理

预处理：根据打家劫舍我们需要现将数据处理一下，先对原数组进行sort升序重新排列，然后用一个新的数组通过下标绝对映射，统计原数组中对应元素的总和，用于打家劫舍问题实现。

这里简单讲解一下，详情可以移步另一篇博客动态规划-LCR 089.打家劫舍-力扣(LeetCode)-CSDN博客

1.状态表示

f[i]表示：选到i位置时，i位置的值必选，此时获得的最大点数

g[i]表示：选到i位置时，i位置的值不选，此时获得的最大点数

2.状态转移方程

f[i]=g[i-1]+arr[i](这里的arr数组是统计重排序数组对应元素总和的数组)

g[i]=max(f[i-1],g[i-1])

3.初始化

f[0]=arr[0],g[0]=0

4.填报顺序

从左向右，两个表一起填

5.返回值

max(f[n-1],g[n-1])(这里的n是原数组的大小)

思考和实践都是不可或缺的，在思考后去实现，740. 删除并获得点数 - 力扣（LeetCode）

三、代码示例

class Solution {
public:int rob(vector<int>& arr) {int n = arr.size();vector<int> f(n),g(n,0);f[0] = arr[0];for(int i = 1;i<n;i++){f[i] = g[i-1]+arr[i];g[i] = max(f[i-1],g[i-1]);}return max(f[n-1],g[n-1]);}int deleteAndEarn(vector<int>& nums) {sort(nums.begin(),nums.end());int n = nums[nums.size()-1];vector<int> arr(n+1);for(int i = 0;i<nums.size();i++){arr[nums[i]] += nums[i];}return rob(arr);}
};