题解 | #[CQOI2007]涂色PAINT#

#include<iostream>
#include<string>
#include<cstring>
using namespace std;

string s;
int dp[55][55];

int main(){
    cin >> s;
    int n = s.size();
    memset(dp, 0x3f, sizeof(dp));
    
    for(int i=0; i<n; i++) dp[i][i] = 1;
    
    for(int len=2; len<=n; len++){
        for(int i=0; i+len-1<n; i++){
            int j = i + len - 1;
            if(s[i] == s[j]){
                dp[i][j] = min(dp[i+1][j], dp[i][j-1]);
            }else{
                for(int k=i; k<j; k++){
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j]);
                }
            }
        }
    }
    cout << dp[0][n-1];
    return 0;
}