动态转化问题之删除并获得点数问题

动态转化问题是算法题中相当重要的一部分，但这类问题也有一定的难度，今天，就让我们来一起学习这其中一种题目。同志们，准备好了吗？？？

一.题目描述

这题目上来一读，是不是有些难理解呀？？，哈哈哈哈哈，别着急，咱先分析一波，看清这题的本质！！

我们来看这一组数据，由于题目中出现了大小关系（删除比抽中数据大1和小1的数据），所以我们现对其进行预处理，进行排序，排序完成之后为

此时，重点来了，我们来举一种符合题目要求的一种方式

此时，我们不禁眼前一亮，蒙了，这是什么情况！！！哈哈哈哈，这不就是那个我们再熟悉不过的打家劫舍问题吗？？？？是的，没错，只是多了一步预处理而已，本质还是那个模型

二.讲解算法原理

在套打家劫舍模型之前，我们需要对这些数据进行排序，这个排序方式不是sort之类的排序。我们需要开辟一个大小等于题目允许的最大点数的数组，然后对nums进行遍历。假设nums[i]=k,那么arr[k]+=k;

for(int i=0;i<nums.size();i++)
{
    arr[nums[i]]+=nums[i};
}

接下来，我们便可以利用arr数组进行相关操作。

1.状态表示

f[i]：表示到达i处时，arr[i]必选，得到的最大点数

g[i]:  表示到达i处时，arr[i]不选，得到的最大点数。

2.状态转移方程

这里。我就不再多说了，大家自己思考一下。

f[i]=g[i-1]+arr[i]

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

3.初始化

题目中，nums[i}>=1,所以arr[0]=0,f[0]和g[0]都为零，我们知道vector默认将元素初始化为0，所以我们不需要再多此一举。

4.填充顺序

两个数组一起填充。

5.返回值

题目中的nums中数据最大为10000，所以我们需要开辟大小均为100001的f,g。

返回f[10000]和g[10000]中的较大值。

三.代码实现