真的是很好的题
要通过左端点 l 和中间点 k 进行比较 然后 n3 来转移
- #include<bits/stdc++.h>
- using namespace std;
- #define maxn 505
- char s[maxn];
- int dp[maxn][maxn],n;
- int main(){
- cin>>n>>s+1;
- memset(dp,0x3f,sizeof dp);
- for(int i=1;i<=n;i++)dp[i][i]=1;
- for(int i=1;i<=n;i++)
- for(int j=1;j<i;j++)
- dp[i][j]=0;
- for(int len=2;len<=n;len++)
- for(int l=1;l+len-1<=n;l++){
- int r=l+len-1;
- if(len==2){
- if(s[l]==s[r])dp[l][r]=1;
- else dp[l][r]=2;
- continue;
- }
- for(int k=l+1;k<=r;k++){
- if(s[l]==s[k])
- dp[l][r]=min(dp[l][r],dp[l+1][k-1]+dp[k][r]);
- else dp[l][r]=min(dp[l][r],dp[l+1][r]+1);
- }
- }
- cout<<dp[1][n]<<endl;
- }
然后是记忆化写法
- #include <bits/stdc++.h>
- using namespace std;
- #define va first
- #define vb second
- typedef long long ll;
- typedef pair<int,int> pii;
- using namespace std;
- const int MN = 510;
- const int INF = 1e9;
- int A[MN],B[MN],D[MN][MN],N,M,K,cnt,tmp,ans,val;
- string S;
- int func(int a, int b){
- if(a>b) return 0;
- if(a==b) return 1;
- if(D[a][b]!=-1) return D[a][b];
- int res = func(a+1,b)+1;
- for(int i=a+1; i<=b; i++){
- if(S[i]==S[a]){
- res = min(res,func(a+1,i-1)+func(i,b));
- }
- }
- return D[a][b] = res;
- }
- int main(){
- cin>> N>> S;
- for(int i=0; i<MN; i++)
- for(int j=0; j<MN; j++)
- D[i][j] = -1;
- cout << func(0,N-1);
- }
来源: http://www.bubuko.com/infodetail-3067712.html