【错题集-编程题】删除相邻数字的最大分数（动态规划 - 线性 dp）

对应牛客题目链接：删除相邻数字的最大分数_牛客题霸_牛客网 (nowcoder.com)

一、分析题目

1、预处理

统计出每一个数字的总和，在 hash 表中选择一些不相邻的数，使得总和最大。

2、状态表示

• f[i]：选到第 i 个位置时，i 位置的元素必选，此时分数的最大总和。
• g[i]：选到第 i 个位置时，i 位置的元不选，此时分数的最大总和。

3、状态转移方程

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

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

4、初始化

f[0] = g[0] = 0

5、返回值

max(f[n], g[n])

二、代码

// 值得学习的代码
#include <iostream>
 
using namespace std;
 
const int N = 1e4 + 10;
 
int sum[N]; // sum[i] 表⽰ i 出现的总和
int n;
int f[N], g[N];
 
int main()
{
    cin >> n;
    int x;
    for(int i = 0; i < n; i++)
    {
        cin >> x;
        sum[x] += x;
    }
 
    for(int i = 1; i < N; i++)
    {
        f[i] = g[i - 1] + sum[i];
        g[i] = max(f[i - 1], g[i - 1]);
    }
 
    cout << max(f[N - 1], g[N - 1]) << endl;
 
    return 0;
}

三、反思与改进

这道题就是打家劫舍系列问题的一个变形，只不过需要自己进行预处理，后面步骤的思路基本一致。这道题没做出来只能说是对动态规划的定义以及递推的过程不熟练，尝试着多用定义去推导后面的公式，再多做一些动态规划主题的题目。