区间dp——好题cf1132F

真的是很好的题

要通过左端点 l 和中间点k进行比较(去找和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);
}