题解 | [CQOI2007]涂色PAINT

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

string target;
int dp[55][55]; // 最多长度为50

// 区间 [l, r] 涂成 target 的最少次数
int dfs(int l, int r) {
    if (l > r) return 0;
    if (dp[l][r] != -1) return dp[l][r];

    int res = dfs(l, r - 1) + 1;  // 先涂前 r-1，然后单独涂 r
    for (int k = l; k < r; ++k) {
        if (target[k] == target[r]) {
            res = min(res, dfs(l, k) + dfs(k + 1, r - 1));
        }
    }

    return dp[l][r] = res;
}

int main() {
    cin >> target;
    int n = target.size();
    // 初始化 dp 为 -1 表示未计算
    for (int i = 0; i <= n; ++i)
        for (int j = 0; j <= n; ++j)
            dp[i][j] = -1;

    cout << dfs(0, n - 1) << endl;
    return 0;
}