[CQOI2007]涂色PAINT

思路：




)

#include 
using namespace std;
typedef long long ll;
const int maxn = 2e3 + 10;
int n;
char s[maxn];
int dp[maxn][maxn];
int main(){
    scanf("%s", s + 1);
    n = strlen(s + 1);
    for(int i = 1; i <= n; i++){
        dp[i][i] = 1;
    }
    for(int len = 2; len <= n; len++){
        for(int l = 1; ; l++){
            int r = l + len - 1; if(r > n) break;
            if(s[l] == s[r]) dp[l][r] = min(dp[l + 1][r], dp[l][r - 1]);
            for(int mid = l; mid < r; mid++){
                if(!dp[l][r]) dp[l][r] = dp[l][mid] + dp[mid + 1][r];
                else dp[l][r] = min(dp[l][r], dp[l][mid] + dp[mid + 1][r]);
            }
        }
    }
    printf("%d\n", dp[1][n]);
    return 0;
}