https://www.luogu.org/problemnew/show/P3146
区间dp，这次设计的状态和一般的有一定的差异。
这次我们定义$dp[i][j]$表示$[i,j]$的可以合并出来最大取值，而不是合并区间$[i,j]$的最大取值。
同样的我们枚举区间长度，枚举左端点，求出右端点。
枚举$i$到$j$之间的每一个分割点，判断两点之间是否可以合并，取价值更高的答案。
$$dp[i][j]=max(dp[i][j],dp[i][k]+1) [dp[i][k]==dp[i][k+1]$$
Question 1:其他的点不需要更新，为什么？
这就要看我们设计的状态了，我们定义的是区间[i,j]可以合并出来的最大值，答案唯一，当然不能用其位置的更新了。
Question 2:答案是什么？
注意这里的答案不一定是$dp[1][n]$,你想当我们计算区间[1,n]时所有的$dp[i][k]!=dp[k+1][j]$那么区间$[1,n]$的答案为$0$，答案在之前已经得出，所以我们在过程中记录一下就好了。
#include <algorithm> #include <iostream> #include <cstring> #include <cstdio> #include <vector> #include <queue> #include <map> using namespace std; #define LL long long #define mod int(1e9+7) int n,a[250],dp[250][250],ans; int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); dp[i][i]=a[i]; //初始化dp数组 } for(int len=2;len<=n;len++) { for(int i=1;i<=n;i++) { int j=i+len-1; if(j>n)break; //超出长度限制 for(int s=i;s<j;s++) { if(dp[i][s]==dp[s+1][j])dp[i][j]=max(dp[i][j],dp[i][s]+1); } ans=max(dp[i][j],ans); //记录答案 } } printf("%d",ans); }
原文：https://www.cnblogs.com/rmy020718/p/9523614.html