题目描述

给定一个字符串 $s$，请将它划分成若干部分，使得每一部分都是回文串。
求最少需要切几刀。

样例

输入："aab"
输出：1
解释：可以划分成：["aa","b"]，所以只用切1刀。

算法

(动态规划) $O(n^2)$

一共进行两次动态规划。

第一次动规：计算出每个子串是否是回文串。
状态表示：$st[i][j]$ 表示 $s[i…j]$ 是否是回文串;
转移方程：$s[i…j]$ 是回文串当且仅当 $s[i]$等于$s[j]$ 并且 $s[i+1…j-1]$ 是回文串；
边界情况：如果$s[i…j]$的长度小于等于2，则$st[i][j] = (s[i] == s[j])$;

在第一次动规的基础上，我们进行第二次动规。
状态表示：$f[i]$ 表示把前 $i$ 个字符划分成回文串，最少划分成几部分；
状态转移：枚举最后一段回文串的起点 $j$，然后利用 $st[j][i]$ 可知 $s[j…i]$ 是否是回文串，如果是回文串，则 $f[i]$ 可以从 $f[j-1]+1$ 转移；
边界情况：0个字符可以划分成0部分，所以 $f[0] = 0$。

题目让我们求最少切几刀，所以答案是 $f[n] - 1$。

时间复杂度分析：两次动规都是两重循环，所以时间复杂度是 $O(n^2)$。

C++ 代码

class Solution {
public:

    int minCut(string s) {
        int n = s.size();
        vector<int>f(n + 1);
        vector<vector<bool>> st(n, vector<bool>(n, false));

        for (int i = 0; i < n; i ++ )
            for (int j = i; j >= 0; j -- )
                if (i - j <= 1) st[j][i] = s[j] == s[i];
                else st[j][i] = s[j] == s[i] && st[j + 1][i - 1];

        f[0] = 0;
        for (int i = 1; i <= n; i ++ )
        {
            f[i] = INT_MAX;
            for (int j = 0; j < i; j ++ )
                if (st[j][i - 1])
                    f[i] = min(f[i], f[j] + 1);
        }
        return max(0, f[n] - 1);
    }
};