題目描述（困難難度）

和 131 題 一樣侄柔，可以在任意位置切割字符串，需要保證切割后的每個子串都是回文串。問最少需要切割幾次诅挑。

和 131 題 用相同的分析方法即可。

解法一 分治

大問題化小問題泛源，利用小問題的結(jié)果拔妥，解決當(dāng)前大問題。

舉個例子达箍。

aabb
先考慮在第 1 個位置切割没龙，a | abb
這樣我們只需要知道 abb 的最小切割次數(shù)，然后加 1缎玫，記為 m1

aabb
再考慮在第 2 個位置切割硬纤，aa | bb
這樣我們只需要知道 bb 的所有結(jié)果，然后加 1赃磨，記為 m2


aabb
再考慮在第 3 個位置切割筝家，aab|b
因為 aab 不是回文串，所有直接跳過

aabb
再考慮在第 4 個位置切割邻辉，aabb |
因為 aabb 不是回文串溪王，所有直接跳過

此時只需要比較 m1 和 m2 的大小，選一個較小的即可值骇。

然后中間的過程求 abb 的最小切割次數(shù)莹菱，求 aab 的最小切割次數(shù)等等，就可以遞歸的去求雷客。遞歸出口的話芒珠，如果字符串的長度為 1,那么它就是回文串了，最小切割次數(shù)就是 0 搅裙。

此外皱卓，和 131 題 一樣，我們用一個 dp 把每個子串是否是回文串部逮，提前存起來娜汁。

public int minCut(String s) {
    boolean[][] dp = new boolean[s.length()][s.length()];
    int length = s.length();
    for (int len = 1; len <= length; len++) {
        for (int i = 0; i <= s.length() - len; i++) {
            int j = i + len - 1;
            dp[i][j] = s.charAt(i) == s.charAt(j) && (len < 3 || dp[i + 1][j - 1]);
        }
    }
    return minCutHelper(s, 0, dp);

}

private int minCutHelper(String s, int start, boolean[][] dp) {
    //長度是 1 ，最小切割次數(shù)就是 0
    if (dp[start][s.length() - 1]) {
        return 0;
    }
    int min = Integer.MAX_VALUE;
    for (int i = start; i < s.length(); i++) {
        //只考慮回文串
        if (dp[start][i]) {
            //和之前的值比較選一個較小的
            min = Math.min(min, 1 + minCutHelper(s, i + 1, dp));
        }
    }
    return min;
}

意料之中兄朋，超時了掐禁。

優(yōu)化方法的話，memoization 技術(shù)，前邊很多題都用到了傅事，比如 87 題缕允，91 題 等等。就是為了解決遞歸過程中重復(fù)解的計算蹭越，典型例子比如斐波那契數(shù)列障本。用一個 map ，把遞歸過程中的結(jié)果存儲起來响鹃。

public int minCut(String s) {
    boolean[][] dp = new boolean[s.length()][s.length()];
    int length = s.length();
    HashMap<Integer, Integer> map = new HashMap<>();
    for (int len = 1; len <= length; len++) {
        for (int i = 0; i <= s.length() - len; i++) {
            int j = i + len - 1;
            dp[i][j] = s.charAt(i) == s.charAt(j) && (len < 3 || dp[i + 1][j - 1]);
        }
    }
    return minCutHelper(s, 0, dp, map);

}

private int minCutHelper(String s, int start, boolean[][] dp, HashMap<Integer, Integer> map) {

    if (map.containsKey(start)) {
        return map.get(start);
    }
    if (dp[start][s.length() - 1]) {
        return 0;
    }
    int min = Integer.MAX_VALUE;
    for (int i = start; i < s.length(); i++) {
        if (dp[start][i]) {
            min = Math.min(min, 1 + minCutHelper(s, i + 1, dp, map));
        }
    }
    map.put(start, min);
    return min;
}

接下來還是一樣的討論驾霜，既然用到了 memoization 技術(shù)，一定就可以把它改寫為動態(tài)規(guī)劃买置，讓我們理一下遞歸的思路粪糙。

如上圖，圖中 a,b,c,d 表示括起來的字符串的最小切割次數(shù)忿项。此時需要求問號處括起來的字符串的最小切割次數(shù)蓉冈。

對應(yīng)于代碼中的下邊這一部分了。

int min = Integer.MAX_VALUE;
for (int i = start; i < s.length(); i++) {
    if (dp[start][i]) {
        min = Math.min(min, 1 + minCutHelper(s, i + 1, dp, map));
    }
}

如下圖倦卖，先判斷 start 到 i 是否是回文串洒擦，如果是的話，就用 1 + d 和之前的 min 比較怕膛。

如下圖，i 后移秦踪，繼續(xù)判斷 start 到 i 是否是回文串褐捻，如果是的話，就用 1 + c 和之前的 min 比較椅邓。

然后 i 繼續(xù)后移重復(fù)上邊的過程柠逞。每次選一個較小的切割次數(shù)，最后問號處就求出來了景馁。

接著 start 繼續(xù)前移板壮，重復(fù)上邊的過程，直到求出 start 等于 0 的最小切割次數(shù)就是我們要找的了合住。

仔細考慮下上邊的狀態(tài)绰精，其實狀態(tài)轉(zhuǎn)移方程也就出來了。

用 dp[i] 表示字符串 s[i,s.lenght-1]透葛，也就是從 i 開始到末尾的字符串的最小切割次數(shù)笨使。

求 dp[i] 的話，假設(shè) s[i,j] 是回文串僚害。

那么 dp[i] = Min(min,dp[j + 1]).

然后考慮所有的 j硫椰，其中 j > i ，找出最小的即可。

當(dāng)然上邊的動態(tài)規(guī)劃和遞歸的方向是一樣的靶草，也沒什么毛病蹄胰。不過我們也可以逆過來，從左往右求奕翔。

這樣的話烤送，用 dp[i] 表示字符串 s[0,i]，也就是從開頭到 i 的字符串的最小切割次數(shù)糠悯。

求 dp[i] 的話帮坚，假設(shè) s[j,i] 是回文串。

那么 dp[i] = Min(min,dp[j - 1]).

然后考慮所有的 j互艾，也就是 j = i, j = i - 1, j = i - 2, j = i - 3.... 试和，其中 j < i ，找出最小的即可纫普。

之前代碼用過 dp 變量了阅悍，所以用 min 變量表示上邊的 dp。

public int minCut(String s) {
    boolean[][] dp = new boolean[s.length()][s.length()];
    int length = s.length();
    for (int len = 1; len <= length; len++) {
        for (int i = 0; i <= s.length() - len; i++) {
            int j = i + len - 1;
            dp[i][j] = s.charAt(i) == s.charAt(j) && (len < 3 || dp[i + 1][j - 1]);
        }
    }
    int[] min = new int[s.length()];
    min[0] = 0;
    for (int i = 1; i < s.length(); i++) {
        int temp = Integer.MAX_VALUE; //找出最小的
        for (int j = 0; j <= i; j++) {
            if (dp[j][i]) {
                //從開頭就匹配昨稼，不需要切割
                if (j == 0) {
                    temp = 0;
                    break;
                //正常的情況
                } else {
                    temp = Math.min(temp, min[j - 1] + 1);
                }
            }
        }
        min[i] = temp;

    }
    return min[s.length() - 1];
}

當(dāng)然我們可以優(yōu)化一下节视，注意到求 dp 和 求 min 的時候都用到了兩個 for 循環(huán)，同樣都是根據(jù)前邊的狀態(tài)更新當(dāng)前的狀態(tài)假栓，所以我們可以把他們糅合在一起寻行。

public int minCut(String s) {
    boolean[][] dp = new boolean[s.length()][s.length()];
    int[] min = new int[s.length()];
    min[0] = 0;
    for (int i = 1; i < s.length(); i++) {
        int temp = Integer.MAX_VALUE;
        for (int j = 0; j <= i; j++) {
            if (s.charAt(j) == s.charAt(i) && (j + 1 > i - 1 || dp[j + 1][i - 1])) {
                dp[j][i] = true;
                if (j == 0) {
                    temp = 0;
                } else {
                    temp = Math.min(temp, min[j - 1] + 1);
                }
            }
        }
        min[i] = temp;

    }
    return min[s.length() - 1];

}

解法二 回溯

回溯法其實就是一個 dfs 的過程。在當(dāng)前字符串找到第一個回文串的位置匾荆，然后切割拌蜘。剩余的字符串進入遞歸，繼續(xù)找回文串的位置牙丽，然后切割简卧。直到剩余的字符串本身已經(jīng)是一個回文串了，就記錄已經(jīng)切過的次數(shù)烤芦。

可以用一個全局變量举娩，保存已經(jīng)切過的次數(shù)，然后到最后更新构罗。

public int minCut(String s) {
    boolean[][] dp = new boolean[s.length()][s.length()];
    int length = s.length();

    for (int len = 1; len <= length; len++) {
        for (int i = 0; i <= s.length() - len; i++) {
            int j = i + len - 1;
            dp[i][j] = s.charAt(i) == s.charAt(j) && (len < 3 || dp[i + 1][j - 1]);
        }
    }
    minCutHelper(s, 0, dp, 0);
    return min;

}

int min = Integer.MAX_VALUE;
//num 記錄已經(jīng)切割的次數(shù)
private void minCutHelper(String s, int start, boolean[][] dp, int num) {
    if (dp[start][s.length() - 1]) {
        min = Math.min(min, num);
        return;
    }
    //嘗試當(dāng)前字符串所有的切割位置
    for (int i = start; i < s.length() - 1; i++) {
        if (dp[start][i]) {
            minCutHelper(s, i + 1, dp, num + 1);
        }
    }
}

同樣出現(xiàn)了超時的問題铜涉。

我們可以像解法一一樣優(yōu)化一下，用一個 map 存一下遞歸過程的中的解绰播。那么問題來了骄噪，解法一是把返回值存了起來，但是這個解法并沒有返回值蠢箩，那么我們存什么呢链蕊？和 115 題 一樣事甜，存增量。什么意思呢滔韵？

我們知道 minCutHelper函數(shù)是計算了從 start 開始的字符串逻谦，全部切割完成后還需要切割的次數(shù)，并且當(dāng)前已經(jīng)切割了 num 次陪蜻。也就是執(zhí)行完下邊的 for 循環(huán)后邦马，如果全局變量min 更新了，那么多切割的次數(shù)就是 min - num宴卖，我們把它存起來就可以了滋将。如果 min 沒更新，那就不用管了症昏。

for (int i = start; i < s.length() - 1; i++) {
    if (dp[start][i]) {
        minCutHelper(s, i + 1, dp, num + 1);
    }
}

這樣只需要在進入遞歸前随闽，判斷之前有沒有算過從 start 開始的字符串所帶來的增量即可。

public int minCut(String s) {
    boolean[][] dp = new boolean[s.length()][s.length()];
    int length = s.length();

    for (int len = 1; len <= length; len++) {
        for (int i = 0; i <= s.length() - len; i++) {
            int j = i + len - 1;
            dp[i][j] = s.charAt(i) == s.charAt(j) && (len < 3 || dp[i + 1][j - 1]);
        }
    }
    HashMap<Integer, Integer> map = new HashMap<>();
    minCutHelper(s, 0, dp, 0, map);
    return min;

}

int min = Integer.MAX_VALUE;

private void minCutHelper(String s, int start, boolean[][] dp, int num, HashMap<Integer, Integer> map) {
    //直接利用之前存的增量
    if (map.containsKey(start)) {
        min = Math.min(min, num + map.get(start));
        return;
    }
    
    if (dp[start][s.length() - 1]) {
        min = Math.min(min, num);
        return;
    }
    for (int i = start; i < s.length() - 1; i++) {
        if (dp[start][i]) {
            minCutHelper(s, i + 1, dp, num + 1, map);

        }
    }
    // min 是否更新了
    if (min > num) {
        map.put(start, min - num);
    }
}

解法三

上邊的解法是一些通用的思考方式肝谭，針對這道題還有一種解法掘宪，在 這里 看到的，也分享一下吧攘烛。

同樣也是動態(tài)規(guī)劃的思路魏滚，用 dp[i] 表示字符串 s[0,i]，也就是從開頭到 i 的字符串的最小切割次數(shù)坟漱。相比于之前更新 dp 的方式鼠次，這里的話把之前存儲每個子串是否是回文串的空間省去了。

基本思想就是遍歷每個字符靖秩，以當(dāng)前字符為中心向兩邊擴展须眷，判斷擴展出來的是否回文串，比如下邊的例子沟突。

0 1 2 3 4 5 6
c f d a d f e
      ^
      c
現(xiàn)在以 a 為中心向兩邊擴展，此時第 2 個和第 4 個字符相等捕传，我們就可以更新
dp[4] = Min(dp[4],dp[1] + 1);
也就是在當(dāng)前回文串前邊切一刀

然后以 a 為中心繼續(xù)向兩邊擴展惠拭，此時第 1 個和第 5 個字符相等，我們就可以更新
dp[5] = Min(dp[5],dp[0] + 1);
也就是在當(dāng)前回文串前邊切一刀

然后繼續(xù)擴展庸论，直到當(dāng)前不再是回文串职辅，把中心往后移動，考慮以 d 為中心聂示，繼續(xù)更新 dp

當(dāng)然上邊是回文串為奇數(shù)的情況域携，我們還需要考慮以當(dāng)前字符為中心的偶數(shù)的情況，是一樣的道理鱼喉。

可以參考下邊的代碼秀鞭。

public int minCut(String s) {
    int[] dp = new int[s.length()];
    int n = s.length();
    //假設(shè)沒有任何的回文串趋观，初始化 dp
    for (int i = 0; i < n; i++) {
        dp[i] = i;
    }

    // 考慮每個中心
    for (int i = 0; i < s.length(); i++) {
        // j 表示某一個方向擴展的個數(shù)
        int j = 0;
        // 考慮奇數(shù)的情況
        while (true) {
            if (i - j < 0 || i + j > n - 1) {
                break;
            }
            if (s.charAt(i - j) == s.charAt(i + j)) {
                if (i - j == 0) {
                    dp[i + j] = 0;
                } else {
                    dp[i + j] = Math.min(dp[i + j], dp[i - j - 1] + 1);
                }

            } else {
                break;
            }
            j++;
        }

        // j 表示某一個方向擴展的個數(shù)
        j = 1;
        // 考慮偶數(shù)的情況
        while (true) {
            if (i - j + 1 < 0 || i + j > n - 1) {
                break;
            }
            if (s.charAt(i - j + 1) == s.charAt(i + j)) {
                if (i - j + 1 == 0) {
                    dp[i + j] = 0;
                } else {
                    dp[i + j] = Math.min(dp[i + j], dp[i - j + 1 - 1] + 1);
                }

            } else {
                break;
            }
            j++;
        }

    }
    return dp[n - 1];
}

總

前邊的解法還是很常規(guī)，從遞歸到動態(tài)規(guī)劃皱坛，利用分治或者回溯，以及 memoization 技術(shù)剩辟，經(jīng)常用到了往扔。最后一個解法贩猎，邊找回文串邊更新 dp ，從而降低了空間復(fù)雜度萍膛，也是很妙了。

更多詳細通俗題解詳見 leetcode.wang 噪馏。