【动态规划】花式解决‘分割回文串 ii’问题（详）

最学习动态规划思想的路上，遇见了‘分割回文串问题’，如临大敌啊，题目听起来蛮简单，思考起来却也没那么容易，比解决问题更头疼的是如何将解决方法进行优化，使得时间空间复杂度尽量的小，经过了反复的挣扎思考，终于总结出来了这一篇 分割回文串 ii 的文章，花式解决该问题，总有一款适合你。

牛客链接

题目：

给出一个字符串s，分割s使得分割出的每一个子串都是回文串

计算将字符串s分割成回文分割结果的最小切割数

例如: 给定字符串s=“aab”,

返回1，因为回文分割结果[“aa”,“b”]是切割一次生成的。

思路分析：

首先，已知字符串s的长度为len，想要求前len个字符串被切割成回文串所需要的最小切割数，就会很自然的想到求前i个字符形成的字符串切割成回文串需要的最小切割数，即为状态F（i）。

然后，会想到前i个字符形成的字符串分割变成回文串需要的最大切割数为i-1。例如字符串”aab”，切2刀形成长度为1的回文串”a”，“a”，“b”。

再然后，关键在于求解最小切割数的过程，这里采取暴力求解，定义变量j,使之小于i，在我们已知状态F（j）的情况下（即前j个字符形成的字符串的最小切割次数），如果[j+1，i]是回文串，那么再来上一 ​?​就可以求出当前用最少的切割次数。那么此时F（i）= min（F（i），F（j）+1），意思就是在上一次求得的前i个字符串的分割次数和这一次求得的次数进行对比，取最小值。（注：这里的[j+1,i]指的是字符串第j+1个字符到第i个字符的意思，并非字符串下标索引，写代码时，转换成索引就应该是求下标为j-1的字符到下标为i的字符形成的字符串是否为回文串）

紧接着，就该实现判断是否为回文串的方法，简单的思想就是，为该方法提供字符串s，提供子串的起始下标start与终点下标end，start

的条件下，使start向后走，end向前走，但凡对应到字符串s中的字符不一样，就说明不是回文串，返回false，如果成功遍历完了循环，说明是回文串，返回true。


最后，将F（len）的值返回。

动归四角度：

1. 状态定义F（i）：字符串s的前i个字符的最小分割次数；
2. 状态间的转移方程定义：F（i）=min（F（i），F（j）+1），0 <= j < i,且F（j）为已知状态，当[j+1,i]为回文串时，执行此状态转移方程
3. 状态的初始化：F（i） = i-1，注意F（0）为-1；

   例如，当字符串为”aa”，因为[1,2]为回文串，F（2）= min（F（2），F（0）+1）=min（1，0）= 0，得到正确答案

4. 返回结果 ：F（s.length())；

案例说明：

为了方便理解，这里采取了更长的字符串”aabaa”,一步步带你走过程。

初级代码

import java.util.*; public class Solution { 
     //判断是否为回文串 public boolean func(String s,int start,int end) { 
     while(start<end) { 
     if(s.charAt(start)!=s.charAt(end)) { 
     return false; } start++; end--; } return true; } public int minCut (String s) { 
     int len = s.length();//字符串的长度 if(len == 0) return 0;//当长度为0时直接返回0 int[] count = new int[len + 1];//用于记录状态 //状态初始化 for(int i = 0;i <= len;i ++) { 
     count[i] = i-1; } for(int i = 1;i <= len;i++) { 
     for(int j = 0;j <= i-1;j++) { 
     if(func(s,j,i-1)) { 
     count[i] = Math.min(count[i],count[j]+1);//状态转移方程 } } } return count[len];//返回结果 } } 

在整个进行状态计算的过程中，两层for循环时间复杂度为O（N²）,判断是否为回文串的方法时间复杂度为O（N），因此总的来说，总的时间复杂度为O（N³）

代码升级

可以看出来，用上面的代码时间复杂度还是比较高的，因此代码还需升级才是

1.回文串动归

首先，关于回文串的判断方法，每次判断是否要进行状态转移方程时都要调用回文串方法，这真的有必要吗，或许也可以使用动态规划的思想将每种字符子串是否为回文串的状态记录下来。

状态四角度：

1. 状态定义F（i，j）：字符区间[i,j]是否为回文串
2. 状态间的转移方程定义F（i，j）：

• 如果i == j，表示单字符，F（i，j） = true；
• 如果j == i+1，表明俩字符是紧挨着的，如果在总字符串s中对应的字符相同，F（i，j）= true，反之F（i，j） = false；
• 其他的情况中，F（i，j） = (s.charAt(i) == s.charAt(j)) && F（i+1，j-1）；

  该转移方程的意思为字符首尾字符相同，且去掉字符区间的首位字符后的字符区间的状态F（i+1，j-1）仍然为回文串才证明[i,j]字符串区间为回文串即F（i，j）= true

3. 状态的初始化：F（i，j） = false
4. 返回结果状态二维布尔类型数组

注：由于在状态转移的过程中，求F（i，j）会只用到之前已经计算过的状态F（i+1，j-1），这就意味着i需要从后向前遍历，使用的是已经更新过结果的值

import java.util.*; public class Solution { 
     //判断是否为回文串 public boolean[][] func2 (String s) { 
     int len = s.length();//字符串的长度 boolean[][] ret = new boolean[len][len]; //记录状态的二维数组，默认值为false //由于i<=j 
     
     for 
     ( 
     int i 
     = len 
     ;i 
     >= 
     0 
     ;i 
     -- 
     ) 
     { 
       
     for 
     ( 
     int j 
     = i 
     ;j 
     <len 
     ;j 
     ++ 
     ) 
     { 
       
     if 
     (i 
     == j 
     ) 
     { 
       ret 
     [i 
     ] 
     [j 
     ] 
     = 
     true 
     ; 
     //单字符比为回文串 
     } 
     else 
     if 
     (j 
     == i 
     + 
     1 
     ) 
     { 
       
     if 
     (s 
     . 
     charAt 
     (i 
     ) 
     == s 
     . 
     charAt 
     (j 
     ) 
     ) 
     { 
       ret 
     [i 
     ] 
     [j 
     ] 
     = 
     true 
     ; 
     //相邻字符相同为回文串 
     } 
     else 
     { 
       ret 
     [i 
     ] 
     [j 
     ] 
     = 
     false 
     ; 
     //相邻字符不同就不是回文串 
     } 
     } 
     else 
     { 
       ret 
     [i 
     ] 
     [j 
     ] 
     = 
     (s 
     . 
     charAt 
     (i 
     ) 
     == s 
     . 
     charAt 
     (j 
     ) 
     ) 
     && ret 
     [i 
     + 
     1 
     ] 
     [j 
     - 
     1 
     ] 
     ; 
     //其余转移情况 
     } 
     } 
     } 
     return ret 
     ; 
     //返回结果 
     } 
     public 
     int minCut 
     ( 
     String s 
     ) 
     { 
       
     int len 
     = s 
     . 
     length 
     ( 
     ) 
     ; 
     if 
     (len 
     == 
     0 
     ) 
     return 
     0 
     ; 
     int 
     [ 
     ] count 
     = 
     new 
     int 
     [len 
     + 
     1 
     ] 
     ; 
     //状态初始化 
     for 
     ( 
     int i 
     = 
     0 
     ;i 
     <= len 
     ;i 
     ++ 
     ) 
     { 
       count 
     [i 
     ] 
     = i 
     - 
     1 
     ; 
     } 
     boolean 
     [ 
     ] 
     [ 
     ] ret 
     = 
     func2 
     (s 
     ) 
     ; 
     //调用判断回文串方法，获得所有字符子串的是否为回文串的情况 
     for 
     ( 
     int i 
     = 
     1 
     ;i 
     <= len 
     ;i 
     ++ 
     ) 
     { 
       
     for 
     ( 
     int j 
     = 
     0 
     ;j 
     <= i 
     - 
     1 
     ;j 
     ++ 
     ) 
     { 
       
     //直接在ret数组中找结果，避免反复调用回文串判断方法 
     if 
     (ret 
     [j 
     ] 
     [i 
     - 
     1 
     ] 
     ) 
     { 
       count 
     [i 
     ] 
     = 
     Math 
     . 
     min 
     (count 
     [i 
     ] 
     ,count 
     [j 
     ] 
     + 
     1 
     ) 
     ; 
     //状态转移方程 
     } 
     } 
     } 
     return count 
     [len 
     ] 
     ; 
     //返回结果 
     } 
     } 
    

在该方法中，判断回文串的方法时间复杂度为O（N²），但因为在主方法中只调用了一次，且回文串判断方法中只更新了一般的值，因此总的时间复杂度为O（N²）~O(2*N²)

2.综合动归

可以看的出来上面的代码还是比较长的，回文串判断方法用到了两层循环，主方法也用到了两层循环，这不也是优化的方向蛮，或许可以把它们放在同一个两层循环中。

注：由于回文串判断方法中的i是一定要从后向前遍历的，因此主函数的初识值就需要调整为count[i] = len - i - 1，返回的结果为F（0）

import java.util.*; public class Solution { 
     public int minCut(String s) { 
     int len = s.length();//字符串的长度 if(len == 0) return 0; int []count = new int[len+1]; //存放最小分割次数状态的数组 boolean [][]p = new boolean[len][len];//存放[i,j]字符区间是否为回文串的二维数组 for(int i = 0; i <= len; i++) count[i] = len - i - 1;//状态初始化 for(int i = len-1;i >= 0;i--){ 
     for(int j = i;j < len;j++){ 
     //j-i<2 条件成立且第一个条件成立包含着单个字符串和相邻字符串的情况 //p[i+1][j-1] 为 ture 且第一个条件成立则代表着其他的回文串状态转移类型 //以上情况有一项成立则F（i，j）为 ture if(s.charAt(i) == s.charAt(j) && (j-i<2||p[i+1][j-1])){ 
     p[i][j] = true; count[i] = Math.min(count[i],count[j+1]+1);//状态转移方程 } } } return count[0];//返回结果 } } 

通过这样的方法，直接将时间复杂度降到了O（N²）

3.奇思妙想

上面几种方法，需要将回文串的判断状态都记录下来，且判断回文串的方法都是从子字符串的两头向中间进行判断，或许有一种方法，可以直接不用记录下来每种子字符串的是否为回文串的状态，并且从中间向两头进行判断回文串。

可以设置两个变量i和j，[i,j]且j==i代表着下标为i的单个字符，必定是回文串，F（j+1）= min（F（j+1），F（i）+1），以此为中心，i--,j++,如果区间两头的字符相同，说明[i-1,j+1]的区间字符串为回文串，在不超出原字符串s的总区间[0,len-1]的循环情况下，重复上面的操作，直到循环条件不成立

回文串可能是奇数个字符，也可能是偶数个字符，上面的情况是奇数个字符的情况，换成偶数个字符的情况只需要判断[i,i+1]是否为回文串，如果是，就参考上面的方式，以此为中心向两头展开，求以[i,i+1]为中心最长的回文串,从而求出每个状态的最小分割数。

案例说明：

import java.util.*; public class Solution { 
     public int minCut(String s) { 
     int len = s.length();//字符串的长度 if(len == 0) return 0; int[] count = new int[len + 1]; for(int i = 0; i <= len; i++) count[i] = i - 1;//状态初始化 for(int i = 0; i < len; i++) { 
     func3(s, i, i, count);//奇数个字符的回文串 func3(s, i, i + 1, count);//偶数个字符的回文串 } return count[len];//返回结果 } private void func3(String s, int i, int j, int[] count) { 
     //不超过字符串s的区间范围且下标i的字符和下标j的字符相等的条件下向两头扩展，得到最长的回文串，以此来求出状态 while(i >= 0 && j < s.length() && s.charAt(i) == s.charAt(j)) { 
     count[j + 1] = Math.min(count[j + 1], count[i] + 1); //状态转移 --i;//左区间扩展一格 ++j;//右区间扩展一格 } return; } } 

完！