中国最好的营销策划公司/南通关键词优化平台

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

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

比如，给出字符串s = "aab"，

返回 1， 因为进行一次分割可以将字符串s分割成["aa","b"]这样两个回文子串

思路：

显然，看到这种最大最小问题，当然是动态规划问题，当然这道题也可以使用DFS来做。

说下动态规划思路，先定义问题结构 ： dp[i] : 代表到s的前i个字符是否为回文。

然后我们就要考虑子问题的结构是什么了。

计算dp[i]的时候，我们从0位置开始，遍历到i，假设现在遍历到了位置j， dp[j]已经是知道的了，我们只需要计算出 j-i 是否是回文就OK了， 如果是，那么 dp[i] = dp[j]+1, 如果不是，计算以下一个，然后得出这些 dp[i]可能的最小值，即为dp[i]的最终值。

下面就有了第一版答案：

    public static int minCut(String s) {boolean[][] isPalindrome= getIsPalindrome(s);// 1. 定义一个数组记录遍历到位置i最小的分割次数int[] dp = new int[s.length()+1];dp[0] = -1;for (int i = 1; i <= s.length(); i++) {int min = Integer.MAX_VALUE;for (int j = 0; j < i; j++) {if(judge(j,i)){min = Math.min(min, dp[j]+1);}}dp[i] = min;}return dp[s.length()];}public static boolean judge(String s){StringBuilder sb = new StringBuilder();for (int i = s.length()-1; i >= 0; i--) {sb.append(s.charAt(i));}return s.equals(sb.toString());}

但是，说空间复杂度太高了，然后，有了下面这个代码，先将判断回文字串的判断矩阵求出来：

    public static int minCut(String s) {boolean[][] isPalindrome= getIsPalindrome(s);// 1. 定义一个数组记录遍历到位置i最小的分割次数int[] dp = new int[s.length()+1];dp[0] = -1;for (int i = 1; i <= s.length(); i++) {int min = Integer.MAX_VALUE;for (int j = 0; j < i; j++) {if(isPalindrome[j][i-1]){min = Math.min(min, dp[j]+1);}}dp[i] = min;}return dp[s.length()];}public static boolean[][] getIsPalindrome(String s){boolean[][] isPalindrome = new boolean[s.length()][s.length()];for (int i = 0; i < s.length(); i++) {isPalindrome[i][i] = true;}for (int i = 0;i<s.length()-1;i++){isPalindrome[i][i+1] = (s.charAt(i)==s.charAt(i+1));}for (int length = 2; length < s.length(); length++) {for (int start = 0;start+length<s.length();start++){isPalindrome[start][start+length] =isPalindrome[start+1][start+length-1] && s.charAt(start)==s.charAt(start+length);}}return isPalindrome;}