面试算法94：最少回文分割

题目

输入一个字符串，请问至少需要分割几次才可以使分割出的每个子字符串都是回文？例如，输入字符串"aaba"，至少需要分割1次，从两个相邻字符’a’中间切一刀将字符串分割成两个回文子字符串"a"和"aba"。

分析

完成一件事需要多个步骤，而且每步可能面临多个选择，这个问题看起来需要用回溯法解决。但由于这个问题没有要求列出所有符合要求的分割方法，而是只需要计算出最少的分割次数，因此这个问题更适合用动态规划来解决。
如果子字符串S[0…i]本身就是一个回文，那么不需要分割就符合要求，此时f（i）等于0。如果子字符串S[0…i]不是一个回文，那么对每个下标j（1≤j≤i）逐一判断子字符串S[j…i]是不是回文。如果是回文，那么这就是一个有效的分割方法，此时的分割次数相当于子字符串S[0…j-1]的分割次数再加1，因为这是将子字符串S[0…j-1]按照要求分割之后再在S[j-1]和S[j]这两个字符中间再分割一次。因此，f（i）就是所有符合条件的j对应的f（j-1）的最小值加1。

解

public class Test {
    public static void main(String[] args) {
        int result = minCut("aaba");
        System.out.println(result);

    }

    public static int minCut(String s) {
        int len = s.length();
        boolean[][] isPal = new boolean[len][len];// 记录S[j...i]字符串是不是回文
        for (int i = 0; i < len; i++) {
            for (int j = 0; j <= i; j++) {
                char ch1 = s.charAt(i);
                char ch2 = s.charAt(j);
                // isPal[j+1][i-1] == true: 表示s[j+1...i-1]是回文字符串
                // i<= j+1: 表示i=j或者j=i-1
                if (ch1 == ch2 && (i <= j + 1 || isPal[j + 1][i - 1])) {
                    isPal[j][i] = true;//
                }
            }
        }

        int[] dp = new int[len];
        for (int i = 0; i < len; i++) {
            if (isPal[0][i]) {
                dp[i] = 0;
            }
            else {
                dp[i] = i;// 每个字符分割一刀，表示最大值
                for (int j = 1; j <= i; j++) {
                    if (isPal[j][i]) {// 在j和j-1中间分割一刀
                        dp[i] = Math.min(dp[i], dp[j - 1] + 1);//遍历从1到i,分割方法的最小值
                    }
                }
            }
        }

        return dp[len - 1];
    }
}