新鲜的AC

#include <iostream>
#include <vector>
#include <string>
#include <climits>

using namespace std;

int minPalindromePartition(string s) {

int n = s.length();
if (n == 0) return 0;
vector<vector<bool>> is_palindrome(n, vector<bool>(n, false));
for (int i = 0; i < n; ++i) {
    is_palindrome[i][i] = true;
}
for (int i = 0; i < n - 1; ++i) {
    if (s[i] == s[i + 1]) {
        is_palindrome[i][i + 1] = true;
    }
}
for (int length = 3; length <= n; ++length) {
    for (int i = 0; i <= n - length; ++i) {
        int j = i + length - 1;
        if (s[i] == s[j] && is_palindrome[i + 1][j - 1]) {
            is_palindrome[i][j] = true;
        }
    }
}

vector<int> dp(n + 1, INT_MAX);
dp[0] = 0; 

for (int i = 1; i <= n; ++i) {
    for (int j = 0; j < i; ++j) {
        if (is_palindrome[j][i - 1]) {
            dp[i] = min(dp[i], dp[j] + 1);
        }
    }
}

return dp[n];

}

int main() {

string s;
cin >> s;
cout << minPalindromePartition(s)-1 << endl;
return 0;

}