题意：
给出一个长度为n的序列，对于相同相邻的两个数x可以替换为一个数x + 1，问该序列的最短长度是多少。
n < = 500
思路：
看到数据范围不难想到是个区间dp
d p [ l ] [ r ]表示区间[ l , r ]能够合并成的最短序列长度。
那么d p [ l ] [ r ] = m i n ( d p [ l ] [ k ] + d p [ k + 1 ] [ r ] )
什么时候[ l , k ]和[ k + 1 , r ]也可以合并呢？当两个区间的最短长度为1并且剩下的数相同时。
记b [ l ] [ r ]表示区间[ l , r ]合并后剩余的数
就可以转移了。
时间复杂度O ( n 3 )
代码：
// Problem: E. Array Shrinking // Contest: Codeforces - Educational Codeforces Round 83 (Rated for Div. 2) // URL: https://codeforces.com/problemset/problem/1312/E // Memory Limit: 256 MB // Time Limit: 2000 ms // // Powered by CP Editor (https://cpeditor.org) #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<set> #include<sstream> using namespace std; typedef long long ll; const int maxn=2e5+100; int a[510],b[510][510],dp[510][510]; int main() { int n;cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++){ dp[i][j]=j-i+1; if(i==j) b[i][i]=a[i]; } for(int len=1;len<=n;len++){ for(int l=1;l+len-1<=n;l++){ int r=l+len-1; for(int k=l;k<=r-1;k++){ dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]); if(dp[l][k]==1&&dp[k+1][r]==1&&b[l][k]==b[k+1][r]){ dp[l][r]=1; b[l][r]=b[l][k]+1; } } } } cout<<dp[1][n]<<endl; return 0; }
思路：
考虑用另一种表示状态：d p [ i ]表示[ 1 , i ]合并后的最短长度，那么最后的答案便是[ 1 , n ]
转移的话，如果说[ k , i ]可以合并为一个数，那么显然d p [ i ] = d p [ k − 1 ] + 1
问题就转化为了如何快速判断区间[ k , i ]能否合并为一个数。
延伸出两种思路：
借助括号匹配的思想，运用栈来判断。具体做法为：枚举右端点，对于每一个右端点，维护一个栈，然后倒着向前枚举，如果当前元素x和栈顶元素相同，弹出栈顶，说明两者合并变为了x + 1。最后如果说栈的大小为1说明该段区间可以合并为一个数。
用区间d p来解，f [ l ] [ r ]表示区间[ l , r ]合并后的数为多少，如果为0则说明无法合并为一个数。枚举中间点，如果说f [ l ] [ k ] = = f [ k + 1 ] [ r ] 则f [ l ] [ r ] = f [ l ] [ k ] + 1
前者的时间复杂度是O ( n 2 )，后者为O ( n 3 )
代码：
栈
// Problem: E. Array Shrinking // Contest: Codeforces - Educational Codeforces Round 83 (Rated for Div. 2) // URL: https://codeforces.com/problemset/problem/1312/E // Memory Limit: 256 MB // Time Limit: 2000 ms // // Powered by CP Editor (https://cpeditor.org) #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<set> #include<sstream> using namespace std; typedef long long ll; const int maxn=2e5+100; int a[510],b[510][510],dp[510]; int main() { int n;cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; for(int r=1;r<=n;r++){ dp[r]=dp[r-1]+1; stack<int>st; st.push(a[r]); for(int l=r-1;l;l--){ int now=a[l]; while(1){ if(st.empty()){ st.push(now);break; } if(now==st.top()) st.pop(),now++; else{ st.push(now);break; } } if(st.size()==1) dp[r]=min(dp[r],dp[l-1]+1); } } cout<<dp[n]<<endl; return 0; }
区间dp
// Problem: E. Array Shrinking // Contest: Codeforces - Educational Codeforces Round 83 (Rated for Div. 2) // URL: https://codeforces.com/problemset/problem/1312/E // Memory Limit: 256 MB // Time Limit: 2000 ms // // Powered by CP Editor (https://cpeditor.org) #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<set> #include<sstream> using namespace std; typedef long long ll; const int maxn=2e5+100; int a[510],f[510][510],dp[510]; int main() { int n;cin>>n; for(int i=1;i<=n;i++) cin>>a[i],f[i][i]=a[i]; for(int len=1;len<=n;len++) for(int l=1;l+len-1<=n;l++){ int r=l+len-1; for(int k=l;k<=r;k++) if(f[l][k]!=0&&f[l][k]==f[k+1][r]) f[l][r]=f[l][k]+1; } memset(dp,0x3f,sizeof dp); dp[0]=0; for(int r=1;r<=n;r++) for(int l=1;l<=r;l++) if(f[l][r]!=0) dp[r]=min(dp[r],dp[l-1]+1); cout<<dp[n]; return 0; }
总结：
d p状态不同决定了时间复杂度的不同，对于某个d p状态来说，又会有好几种解法。
参考：
博客1
博客2
