题目描述

给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。

返回符合要求的最少分割次数。

样例

输入: "aab"
输出: 1
解释: 进行一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。

算法1

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

* 根据上一题的分析，g数组存储的g[i][j]表示s[i~j]是否是回文串
* f[i]表示s[1~i]最少可以分为几段回文串
* 集合的划分：f[i]可以通过s[1~i],s[2~i],...,s[i~i]是否是回文串划分，取划分出来的回文串数量最小值。

Java 代码

class Solution {
    public int minCut(String s) {
        int n = s.length();
        s = " " + s;
        boolean[][] g = new boolean[n+1][n+1];
        int[] f = new int[n+1];
        Arrays.fill(f,Integer.MAX_VALUE);

        for(int j = 1; j <= n; j++){
            for(int i = 1; i <= j; i++){
                if(i == j) g[i][j] = true;
                else if(s.charAt(i) == s.charAt(j)){
                    if(i + 1 > j - 1 || g[i+1][j-1]) g[i][j] = true;
                }
            }
        }
        f[0] = 0;
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= i; j++){
                if(g[j][i]){
                    f[i] = Math.min(f[i],f[j-1]+1);
                }
            }
        }
        return f[n]-1;
    }
}