题解 | [CQOI2007]涂色PAINT

#include <bits/stdc++.h>
using namespace std;

const int N = 60;
string str;
int dp[N][N];

int main(){
    cin>>str;
    int n = str.size();
    memset(dp,0x3f,sizeof dp);
    str = ' ' + str;

    for(int i = 0;i<n;i++){
        for(int j = 1;j+i<=n;j++){
            int k = j + i;
            if(j==k) dp[j][k] = 1;
            else if(str[j]==str[k]) dp[j][k] = min(dp[j+1][k],dp[j][k-1]);
            else{
                for(int k2 = j;k2<k;k2++){
                    dp[j][k]  = min(dp[j][k],dp[j][k2]+dp[k2+1][k]);
                }
            }
        }
    }
    cout<<dp[1][n];

    return 0;
}

左边界等于右边界时，dp[j][k]=1,如果str[j]==str[kl]那么就取min(dp[j+1][k],dp[j][k-1])，否则取他们之间的最小值

#牛客春招刷题训练营#https://www.nowcoder.com/discuss/727521113110073344