题面：

戳这里

题意：

给你n个数，让你找出差分序列的个数并取模（直接说人话）

思路：

常用的解题步骤：

第一步：确定子问题。 对于本题子问题即为当前有i个塔，他的方案数为多少。

第二步：确定状态：这部非常重要，一个好的状态描述可以让你更容易想出状态转移 ，但是也很困难，需要仔细考虑。根据子问题来确定。找出可以描述每个状态的变量，本题的状态由以 i 塔结尾的公比为 d 的等差数列 描述。dp[i][d]表示以第 i 个塔结尾公差为 d 的等差数列方案数。（状态应该都能一眼看出来）

第三步：推到出状态转移方程，这里要注意你的状态转移方程是不是满足所有的条件， 注意不要遗漏。

这是dp问题的第二个重点，可以先寻找规律。如本题如果确定了状态描述，则很容易看出，第 i 个塔之前如果存在与第 i 个塔高度差为d的塔 j ，dp[i][d]则可以由dp[j][d] 转移。

本题的状态转移为：

if(d[i]-d[j]==d) dp[i][d]+=dp[j][d]+1;(这个方程是难点，建议反复观看推导过程) (这个式子死活退不出来，离谱)

第四步：确定边界条件：先根据题目的限制条件来确定题目中给出的边界条件是否能直接推导出，如果不行也可以尝试从边界条件反推（举个例子：a(n)→a(2)有递推关系，但是a(2)→a(1)不符合上述递推关系， 我们就可以考虑用a(1)来倒推出a(2)，然后将递推的终点设置为a(2)）;

第五步：确定实现方式：这个依照个人习惯 就像是01背包的两层for循环的顺序，也可以记忆化搜索，一般搜索会更好理解一些

第六步：确定优化方法：很多时候你会发现走到这里步的时候你需要返回第1步重来。首先考虑降维问题（优化内存）， 优先队列、四边形不等式（优化时间）等等。

总结了这么多来看看代码

#include<bits/stdc++.h>
using namespace std;
const int mh = 2e4;
const int mod = 998244353;
long long read()
{
	long long x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int n;
int h[1010];
int dp[1010][mh*2+10];
long long ans;
int main()
{
	n=read();
	for(int i=1;i<=n;i++) h[i]=read();
	for(int i=1;i<=n;i++)
	{
		ans++;//一个塔也算做答案
		for(int j=1;j<i;j++)
		{
			long long d=h[i]-h[j];
			dp[i][d+mh]+=dp[j][d+mh]+1;
			dp[i][d+mh]%=mod;
			ans+=dp[j][d+mh]+1;
			ans%=mod;
		}
	}
	cout<<ans<<endl;
	return 0;
}

总结

本题考察的是动态规划求方案数类问题的解法，状态大概都能找对，就是转移方程太离谱了，死活退不出来(可能是我太菜了吧)，作为一道绿题还是挺考验思维的，好题+1.

至此本题完，下面总结点干货

常用方法

以下是方法，但是不要局限在这里，方法是无限的

（1）模型匹配法：熟练记忆并且理解LIS、LCS、01背包、完全背包、区间模型、树状模型。基本就是将原模型加以变化后加以套用

（2）三要素法：

①先确定阶段：如数塔问题， 先确定当前选的是第几层。

②先确定状态：这是最常用的绝大多数的DP都是这么做的。

③先确定决策：背包问题（选还是不选第i种物品）

（3）寻找规律法：从小的状态开始推， 耐心找规律， 或者可以在本地暴力打表， 暴力出奇迹， 不打2、3页那都不叫打表，几年省赛彻底领悟了，不想说啥。

（4）边界条件法： 一般边界时容易导出状态关系的地方

（5）增加约束条件法：这条就对应着上文的消除后效性