Palindrome Partitioning II -- LeetCode

原題鏈接: http://oj.leetcode.com/problems/palindrome-partitioning-ii/
這道題跟Palindrome Partitioning非常類似，區別就是不需要返回所有滿足條件的結果，而只是返回最小的切割數量就可以。做過Word Break的朋友可能馬上就會想到，其實兩個問題非常類似，當我們要返回所有結果（Palindrome Partitioning和Word Break II）的時候，使用動態規劃會耗費大量的空間來存儲中間結果，所以沒有明顯的優勢。而當題目要求是返回某個簡單量（比如Word Break是返回能否切割，而這道題是返回最小切割數）時，那麼動態規劃比起brute force就會有明顯的優勢。這道題先用Palindrome Partitioning中的方法建立字典，接下來動態規劃的方式和Word Break是完全一樣的，我們就不再細說了，不熟悉的朋友可以看看Word Break的分析哈。因為保存歷史信息只需要常量時間就能完成，進行兩層循環，時間復雜度是O(n^2)。空間上需要一個線性數組來保存信息，所以是O(n)。代碼如下：

public int minCut(String s) {
    if(s == null || s.length()==0)
        return 0;
    boolean[][] dict = getDict(s);
    int[] res = new int[s.length()+1];
    res[0] = 0;
    for(int i=0;i=0;i--)
    {
        for(int j=i;j這個問題和Word
 Break可以說是一個題目，這裡多了一步求解字典。如果求解所有結果時，他們沒有多項式時間的解法，復雜度取決於結果數量，而當求解某一種統計的特殊量時，用動態規劃就會很大的優勢，可以降低時間復雜度。