解法一：【遞歸】
對(duì)于一個(gè)字符串，先找到第一段回文子字符串，然后再求余下的子串的最少分割數(shù)，然后再加1，就可以得到一種分割結(jié)果，遍歷所以這樣的解法，就可以求出最小的分割次數(shù)。
public class MinCut {
private boolean isPalindrome(String s){
int len = s.length();
if(len>1){
for(int i=0;i<len/2;++i){
if(s.charAt(i)!=s.charAt(len-i-1)){
return false;
}
}
}
return true;
}
public int minCut(String s){
if(isPalindrome(s)){
return 0;
}
int min = 99999;
int len =s.length();
for(int i=1;i<len;++i){
String ss = s.substring(0,i);
if(isPalindrome(ss)){
int result = minCut(s.substring(i))+1;
if(result<min){
min = result;
}
if(min<=1){
break;
}
}
}
return min;
}
public static void main(String[] args) throws IOException {
long tick = System.currentTimeMillis();
MinCut m = new MinCut();
int result = m.minCut("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa");
System.out.println("result:"+result+",costs:"+(System.currentTimeMillis()-tick)+" ms");
}
}
這樣算法雖然可行，但是效率很低，對(duì)于小字符串還可以工作，對(duì)于上面的長度為1400+的字符串就慢的驚人。
因?yàn)橛写罅康闹貜?fù)計(jì)算。改進(jìn)一下，把已經(jīng)計(jì)算好的子串的最少分割次數(shù)的結(jié)果記錄下來，應(yīng)該能快很多。
Map<String,Integer> memos = new HashMap<String,Integer>();
public int cut(String s){
if(isPalindrome(s)){
return 0;
}
if(memos.containsKey(s)){
return memos.get(s).intValue();
}
int min = 99999;
int len =s.length();
for(int i=1;i<len;++i){
String ss = s.substring(0,i);
if(isPalindrome(ss)){
int result = cut(s.substring(i))+1;
if(result<min){
min = result;
}
if(min<=1){
break;
}
}
}
memos.put(s, min);
return min;
}
public int minCut(String s) {
memos.clear();
return cut(s);
}
果然，優(yōu)化后的結(jié)果要快很多，在我的機(jī)器上大概1200ms就可以求出結(jié)果了。
解法二：【動(dòng)態(tài)規(guī)劃】
其實(shí)這個(gè)問題是一個(gè)典型的動(dòng)態(tài)規(guī)劃問題。問題的最優(yōu)解可以歸結(jié)為兩個(gè)子問題的最優(yōu)解，再加上1就可以了，使用動(dòng)態(tài)規(guī)劃記錄所有的中間狀態(tài)就可以降低重復(fù)計(jì)算。
狀態(tài)轉(zhuǎn)移公式如下：
minCut(s,i,j) = 0 if(s[i..j] 是回文的）
minCut(s,i,j) = min(minCut(s,i,k)+minCut(s,k+1,j))(i<k<j) |
為了減少回文的判斷，使用了兩個(gè)數(shù)組，M用來記錄最優(yōu)分割次數(shù)，P用來保存子串的回文判斷結(jié)果。
代碼如下：
public int minCut(String s){
int totalLength = s.length();
char[] ch=s.toCharArray();
int [][] M = new int[totalLength][totalLength];
boolean [][] P = new boolean[totalLength][totalLength];
for(int len=1;len<=totalLength;++len){
for(int i=0;i<totalLength-len+1;++i){
int j = i+len-1;
if(len==1){
P[i][j]=true;
}
else if(len==2){
P[i][j]=(ch[i]==ch[j]);
}
else{
P[i][j]=(ch[i]==ch[j]) && P[i+1][j-1];
}
if(P[i][j]){
M[i][j] = 0;
}
else{
int min = 99999;
for(int k=i;k<j;++k){
int t = M[i][k]+M[k+1][j]+1;
if(min>t){
min = t;
}
}
M[i][j] = min;
}
}
}
return M[0][totalLength-1];
}
這個(gè)算法的復(fù)雜度是O(n
3）的復(fù)雜度，使用了三層循環(huán)。對(duì)于上面的字符串大概需要花4000ms左右的時(shí)間。
有沒有辦法把復(fù)雜度降為O(n
2)呢？對(duì)于長度為L的字符串的最少切割次數(shù)等于L-1的切割次數(shù)+1或者如果最后一個(gè)字符能夠跟前面的子字符串構(gòu)成回文的話，就等于去除該子串的剩余部分的切割次數(shù)+1。
有些拗口，還是看狀態(tài)轉(zhuǎn)移公式吧：
minCut(j)= min(
minCut(j-i-1)+1: if s(i,j) is palindrom
where 0<=i<j ,
minCut(j-1)+1) |
同時(shí)優(yōu)化一下回文的判斷，減少函數(shù)調(diào)用。
private boolean isPalindrome(char[] ch, int i,int j){
while(i<j){
if(ch[i]!=ch[j]){
return false;
}
++i;
--j;
}
return true;
}
public int minCut(String s){
int totalLength = s.length();
int[] M = new int[totalLength];
char[] ch = s.toCharArray();
M[0]=0;
for(int i=1;i<totalLength;++i){
int min = 99999;
for(int j=0;j<=i;++j){
int cut = 99999;
if(isPalindrome(ch,j,i)){
if(j>0){
cut = M[j-1]+1;
}
else{
cut = 0;
}
if(min>cut){
min = cut;
}
}
}
M[i]=min;
}
return M[totalLength-1];
}
優(yōu)化后的結(jié)果，大概只需要200ms左右了。