删除并获得点数

问题描述

删除并获得点数

解题思路

本题的解题思路就是将我们原问题中的数据进行重新整理，统计到一个用数组实现的哈希表中，哈希表中记录原数组中出现的每一个元素的个数。然后我们再对这个数组用打家劫舍模型处理即可

确定本题的状态表示

dp[i]表示的是

确定本题的状态转移方程

根据已知条件：dp[0]=0，dp[1]=1，dp[2]=1
本题的状态转移方程是：

填表求值

根据初始条件和状态转移方程，确定填表顺序，进而逐步填满dp表，最终返回题目要的结果

代码实现

class Solution {
public:int deleteAndEarn(vector<int>& nums) {const int N = 10001;// 1. 预处理int arr[N] = {0};for(auto x : nums) arr[x] += x;// 2. 在 arr 数组上，做一次“打家劫舍”问题// 创建 dp 表vector<int> f(N);auto g = f;// 填表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]);}
};

自己写的

class Solution {
public:int deleteAndEarn(vector<int>& nums) {const int N=10001;vector<int> hash(N,0);vector<int> f(N),g(N);f[0]=hash[0];g[0]=0;for(auto & x:nums) hash[x]+=x;for(int i=1;i<N;i++){f[i]=g[i-1]+hash[i];g[i]=max(f[i-1],g[i-1]);}return max(f[N-1],g[N-1]);}
};