【区间dp-回文-3】回文最少分割

同leet 132. 分割回文串 II

描述

给定一个字符串，返回把str全部切割成回文串的最少切割数。

输入描述：

输出包含一行字符串，代表str(1≤lengthstr≤5000)(1≤lengthstr​≤5000)。

输出描述：

输出一个整数，代表把str全部切割成回文串的最小切割数。

示例1

输入：

ABA

输出：

0

说明：

本身是回文串，不需要切割，直接输出0

示例2

输入：

ABCBAEEE

输出：

1

说明：

切割1次，变为“ABCBA”和“EEE”

备注：

时间复杂度O(n2)O(n2),额外空间复杂度O(n2)O(n2)。

这个在用区间型动态规划构建dp[l][r]的基础上，同时也用上了划分型动态规划。简单来说从任何位置构建的回文子串可能不止有一个，当前位置dp答案可以由过去的多种方案的dp值推出来,取各次推出的最小值。

题目实际是想找字符串全部由回文子串 串联构成的 不重叠的 最少回文子串个数

分析：1）使用动态规划在构建dp[l][r]的时候会遇到s中所有回文子串。

2）用动态规划dp2[i]表示s字符串上[0,i-1]闭区间长度为i的字符串的答案--“所有可能的分割方案”分割出来的回文子串数量

3）当构建dp[l][r]时遇到回文子串的时候，可以推断：[0，r]区间长度为 r+1 的字符串对应结果：

dp2[r + 1] = Math.min( dp2[r + 1], dp2[l] + 1); //在dp2[l]的基础上增加1个回文子串

4) 另外dp2[r+1]初始值是dp2[r]+1, 长度为r的字符串增加1个字符变成长度为r的字符串，增加的1个字符构成1个回文子串

综上分析，代码如下：

     public int minCut(String str) {
        char[] s = str.toCharArray();
        int n = s.length;
        boolean[][] dp = new boolean[n][n];
        int[] dp2 = new int[n + 1];
        for (int r = 0; r < n; r++) {
            dp2[r + 1] = dp2[r] + 1;
            for (int l = r; l >= 0; l--) {
                if ( l == r || (s[l] == s[r] && (l + 1 == r || dp[l + 1][r - 1])) ) {
                    dp[l][r] = true;
                    dp2[r + 1] = Math.min( dp2[r + 1], dp2[l] + 1);
                }
            }
        }
        return dp2[n] - 1; //分割数=子串数量-1
    }