线性dp

题目背景
建筑大师最近在跟着数学大师 ljt12138 学数学，今天他学了等差数列，ljt12138 决定给他留一道练习题。

题目描述
ljt12138 首先建了 nn 个特斯拉电磁塔，这些电塔排成一排，从左到右依次标号为 11 到 nn ，第 ii 个电塔的高度为 h[i]h[i] 。

建筑大师需要从中选出一些电塔，然后这些电塔就会缩到地下去。这时候，如果留在地上的电塔的高度，从左向右构成了一个等差数列，那么这个选择方案就会被认为是美观的。

建筑大师需要求出，一共有多少种美观的选择方案，答案模 998244353998244353 。

注意，如果地上只留了一个或者两个电塔，那么这种方案也是美观的。地上没有电塔的方案被认为是不美观的。

同时也要注意，等差数列的公差也可以为负数。

输入格式
第一行一个正整数 nn 。

第二行 nn 个非负整数，第 ii 个整数是第 ii 个电塔的高度 h[i]h[i] 。

输出格式
输出一个整数，表示美观的方案数模 998244353998244353 的值。

这题我觉得还是特别难的，要想到动态规划f数组定义为以i结尾，公差为j的等差数列的方案数，如果定义成只考虑前i个就很难转移，想想转移的复杂度，如果枚举ijk n^2v必定超时，我们发现 当只有a[i]-a[j]==k时才会转移，我们可以优化一下 只枚举 i和j，然后想想如何转移
我们以i结尾的前一个数j当作划分依据，我一开始以为是f[i][a[i]-a[j]+maxh]+=f[j][a[i]-a[j]+maxh] 结果发现是不对的 ，因为a[j]和a[i]这两个也可以组成等差数列且公差是ai-aj ，那么就应该是f[i][a[i]-a[j]+maxh]+=f[j][a[i]-a[j]+maxh]+1了，注意坑点，公差可以是负数，那么我们加一个最大值作为偏移量，防止越界。
ac代码：

#include<iostream>
#include<cstring>
#include<map>
#include<vector>
#include<cmath>
#include<algorithm>
#include<set>
#define x first
#define y second
using namespace std;
typedef long long ll;
const int N=1010;
const int M=40010;
typedef pair<int,int> pii;
int a[N];
int f[N][M];	//考虑前i个包括第i个 公差为d的方案数
const int mod=998244353;
int n;
int main()
{
   
	// 2 2 4
	// f[1][2]=0;
	// f[2][2]=0;
	// f[4][2]=2;
	// 3 5 7 9
	// 3 5 7 9
	// 3 5 
	// f[2][1]=1
	// f[3][1]=2
	//f[i][k]
	cin >> n; 
	int maxh=0;
	for(int i=1;i<=n;i++)
		cin>>a[i] , maxh=max(maxh,a[i]);
	//cout<<maxh<<endl;
	for(int i=1;i<=n;i++)
		f[i][0]=1;
	int res=0;
	for(int i=1;i<=n;i++)
		{
   
			for(int j=1;j<i;j++)
				{
   
					f[i][a[i]-a[j]+maxh]= (f[i][a[i]-a[j]+maxh] + 1 +f[j][a[i]-a[j]+maxh])%mod; 	
					
				}
			for(int j=0;j<M;j++)
			res=(res+f[i][j])%mod;	
			}

	cout<<res<<endl;
	return 0;
}