poj 1159 区间dp （用int竟然会爆空间interesting）

#include<cstdio> #include<iostream> #include<cstring> #include<string> #include<algorithm> using namespace std; const int maxn=5005; char s[maxn]; short res[maxn][maxn];//用int会爆空间，23333 int main() { int n,i,j,len; scanf("%d",&n); scanf("%s",s); len=strlen(s); for(i=1;i<len;i++) for(j=0;j+i<len;j++) if(s[j]==s[j+i]) res[j][j+i]=res[j+1][j+i-1]; else res[j][j+i]=min(res[j][j+i-1],res[j+1][j+i])+1; printf("%d\n",res[0][len-1]); return 0; }