[数据结构与算法]动态规划解决回文串分割问题

问题描述：

(1)解法一：
回文串：正读和反读都一样的字符串，比如noon，level，字符串左右对称。
如何判断一段字符串为回文串？
循环判断首尾元素是否相同，如果全部相同，则是回文串

状态：F(i): 到第i个字符需要的最小分割数
状态递推：
F(i) = min{F(i), F(j)+1}, where j<i && j+1到i是回文串
上式表示如果从j+1到i判断为回文字符串，且已经知道从第1个字符 到第j个字符的最小切割数，那么只需要再切一次，就可以保证 1–>j, j+1–>i都为回文串。
初始化：
F(i) = i - 1
上式表示到第i个字符需要的最大分割数 比如单个字符只需要切0次，因为单子符都为回文串 2个字符最大需要1次，3个2次。
返回结果： F(n)

代码：

import java.util.*;
public class Solution {
    //判断是否是回文串
    public boolean isPal(String s,int start,int end){
        while(start < end){
            if(s.charAt(start) != s.charAt(end)){
                return false;
            }
            start++;
            end--;
        }
        return true;
    }
    /**
     * 
     * @param s string字符串 
     * @return int整型
     */
    public int minCut (String s) {
        // write code here
        int len=s.length();
        if(len==0)
            return 0;
        int[] minCut=new int[len+1];
        //F(i)初始化
        for(int i=0;i<=len;i++){
            minCut[i]=i-1;
        }
        for(int i=1;i<=len;i++){
            for(int j=0;j<i;j++){
                //F(i) = min{F(i), 1 + F(j)}, where j<i && j+1到i是回文串 
                //从最长串判断，如果从第j+1到i为回文字符串 
                //则再加一次分割，从1到j，j+1到i的字符就全部分成了回文字符串
                if(isPal(s,j,i-1)){
                    minCut[i]=Math.min(minCut[i],minCut[j]+1);
                }
            }
        }
        return minCut[len];
    }
}

运行截图：

上述方法两次循环时间复杂度是O(n^2),
判断回文串时间复杂度是O(n)
所以总时间复杂度为O(n^3) 对于过长的字符串
在OJ的时候会出现TLE(Time Limit Exceeded)
判断回文串的方法可以继续优化，使总体时间复杂度将为O(n^2)
判断回文串，这是一个“是不是”的问题，所以也可以用动态规划来实现

(2)解法二 ：方法一的优化

判断回文串：动态规划
状态：F(i,j): 字符区间 [i,j] 是否为回文串
递推公式： **F(i,j): true->{s[i]==s[j] && F(i+1,j-1)} OR false
**>上式表示如果字符区间首尾字符相同且在去掉区间首尾字符后字符区间仍为回文串， 则原字符区间为回文串 从递推公式中可以看到第i处需要用到第i+1处的信息，所以i应该从字符串末尾遍历
初始化： F(i,j) = false
返回结果： 矩阵F(n,n), 只更新一半值（i <= j），n^2 / 2

代码：

import java.util.*;
public class Solution{
    public boolean[][] getMat(String s){
        int len=s.length();
        boolean[][] Mat=new boolean[len][len];
        for(int i=len-1;i>=0;i--){
            for(int j=i;j<len;j++){
                if(j==i)
                    //单字符为回文字符串
                    Mat[i][j]=true;
                else if(j==i+1){
                    //相邻字符如果相同，则为回文字符串
                    if(s.charAt(i)==s.charAt(j))
                        Mat[i][j]=true;
                    else
                        Mat[i][j]=false;
                }else{
                    Mat[i][j]=(s.charAt(i)==s.charAt(j)) && Mat[i+1][j-1];
                }
            }
        }
        return Mat;
    }
    /**
     * 
     * @param s string字符串 
     * @return int整型
     */
    public int minCut (String s) {
        // write code here
        int len=s.length();
        if(len==0)
            return 0;
        boolean[][] Mat=getMat(s);
        int[] minCut=new int[len+1];
        //F(i)初始化
        for(int i=0;i<=len;i++){
            minCut[i]=i-1;
        }
        for(int i=1;i<=len;i++){
            for(int j=0;j<i;j++){
                //F(i) = min{F(i), 1 + F(j)}, where j<i && j+1到i是回文串 
                //从最长串判断，如果从第j+1到i为回文字符串 
                //则再加一次分割，从1到j，j+1到i的字符就全部分成了回文字符串
                if(Mat[j][i-1]){
                    minCut[i]=Math.min(minCut[i],minCut[j]+1);
                }
            }
        }
        return minCut[len];
    }
}

运行结果:

上述方法判断回文串时间复杂度O(n^2)
主方法两次循环时间复杂度O(n^2)
总体时间复杂度O(n^2) ~ O(2 * n^2) = O(n^2) + O(n^2)