算法思路

C ++代码

class Solution {
public:
    int minCut(string s) {
        int n = s.size();
        vector<int> f(n + 1, 0);
        for (int i = 0; i <= n; i ++) f[i] = i - 1;
        //从0开始初始化

        for (int i = 1; i <= n; i ++) { //字符串中下标从0开始
            for (int j = 0; i - j >= 1 && i + j <= n && s[i - j - 1] == s[i + j - 1]; j ++) //长度为奇数的回文串
                f[i + j] = min(f[i + j], f[i - j - 1] + 1);

            for (int j = 1; i - j + 1 >= 1 && i + j <= n && s[i - j] == s[i + j - 1]; j ++) //长度为偶数的回文串
                f[i + j] = min(f[i + j], f[i - j] + 1);
        }

        return f[n];
    }
};