T1 潘

较水吧，直接区间dp

dp[i][j]显然表示区间答案，开头预处理出一个的和两个的

考虑转移

若当前的str[i]==str[j]，必可以和原来的最后一段形成回文，然后一起删掉

若str[i]!=str[j]，就枚举断点就ok了

#include<bits/stdc++.h>
using namespace std;
#define int long long
int dp[1005][1005],n;
string str;
signed main() {
    for (int i=0;i<1000;++i) {
        for (int j=0;j<1000;++j) {
            dp[i][j]=1000000000;
        }
    }
    cin>>n>>str;
    for (int i=0;i<=n;++i) dp[i][i]=1;
    for (int i=0;i<n-1;++i) {
        if (str[i]==str[i+1]) dp[i][i+1]=1;
        else dp[i][i+1]=2;
    }
    for (int len=3;len<=n;++len) {
        for (int i=0;i+len<=n;++i) {
            int j=i+len-1;
            if (str[i]==str[j]) dp[i][j]=dp[i+1][j-1];
            for (int k=i;k<j;++k) {
                dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);
            }
        }
    }
    printf("%lld\n",dp[0][n-1]);
    return 0;
} 

T2 膜

#include<bits/stdc++.h>usingnamespacestd; #define int long longint dp[1005][1005],n; string str; signed main() { for (int i=0;i<1000;++i) { for (int j=0;j<1000;++j) { dp[i][j]=1000000000; } } cin>>n>>str; for (int i=0;i<=n;++i) dp[i][i]=1; for (int i=0;i<n-1;++i) { if (str[i]==str[i+1]) dp[i][i+1]=1; else dp[i][i+1]=2; } for (int len=3;len<=n;++len) { for (int i=0;i+len<=n;++i) { int j=i+len-1; if (str[i]==str[j]) dp[i][j]=dp[i+1][j-1]; for (int k=i;k<j;++k) { dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]); } } } printf("%lld\n",dp[0][n-1]); return0; } /* input: 7 abbcdca output: 2 input: 8 bbabbbaa output: 3 */