分割回文字符串

da183 · da183 · commit f9a0335eb272 · 2020-07-12T19:28:21.000+08:00
diff --git a/basic_algorithm/dp.md b/basic_algorithm/dp.md
@@ -283,97 +283,60 @@ bool canJump(vector<int>& nums) {
 > &#25968;&#32452;&#20013;&#30340;&#27599;&#20010;&#20803;&#32032;&#20195;&#34920;&#20320;&#22312;&#35813;&#20301;&#32622;&#21487;&#20197;&#36339;&#36291;&#30340;&#26368;&#22823;&#38271;&#24230;&#12290;
 > &#20320;&#30340;&#30446;&#26631;&#26159;&#20351;&#29992;&#26368;&#23569;&#30340;&#36339;&#36291;&#27425;&#25968;&#21040;&#36798;&#25968;&#32452;&#30340;&#26368;&#21518;&#19968;&#20010;&#20301;&#32622;&#12290;
 
-```go
-// v1&#21160;&#24577;&#35268;&#21010;&#65288;&#20854;&#20182;&#35821;&#35328;&#36229;&#26102;&#21442;&#32771;v2&#65289;
-func jump(nums []int) int {
-    // &#29366;&#24577;&#65306;f[i] &#34920;&#31034;&#20174;&#36215;&#28857;&#21040;&#24403;&#21069;&#20301;&#32622;&#26368;&#23567;&#27425;&#25968;
-    // &#25512;&#23548;&#65306;f[i] = f[j],a[j]+j >=i,min(f[j]+1)
-    // &#21021;&#22987;&#21270;&#65306;f[0] = 0
-    // &#32467;&#26524;&#65306;f[n-1]
-    f := make([]int, len(nums))
-    f[0] = 0
-    for i := 1; i < len(nums); i++ {
-        // f[i] &#26368;&#22823;&#20540;&#20026;i
-        f[i] = i
-        // &#36941;&#21382;&#20043;&#21069;&#32467;&#26524;&#21462;&#19968;&#20010;&#26368;&#23567;&#20540;+1
-        for j := 0; j < i; j++ {
-            if nums[j]+j >= i {
-                f[i] = min(f[j]+1,f[i])
-            }
-        }
-    }
-    return f[len(nums)-1]
-}
-func min(a, b int) int {
-    if a > b {
-        return b
-    }
-    return a
-}
-```
-
-```go
-// v2 &#21160;&#24577;&#35268;&#21010;+&#36138;&#24515;&#20248;&#21270;
-func jump(nums []int) int {
-    n:=len(nums)
-    f := make([]int, n)
-    f[0] = 0
-    for i := 1; i < n; i++ {
-        // &#21462;&#31532;&#19968;&#20010;&#33021;&#36339;&#21040;&#24403;&#21069;&#20301;&#32622;&#30340;&#28857;&#21363;&#21487;
-        // &#22240;&#20026;&#36339;&#36291;&#27425;&#25968;&#30340;&#32467;&#26524;&#38598;&#26159;&#21333;&#35843;&#36882;&#22686;&#30340;&#65292;&#25152;&#20197;&#36138;&#24515;&#24605;&#36335;&#26159;&#27491;&#30830;&#30340;
-        idx:=0
-        for idx<n&&idx+nums[idx]<i{
-            idx++
+```c++
+int jump(vector<int>& nums) {
+    int size = nums.size();
+    vector<int> cache(size);
+    cache[0] = 0;
+    // cache[i + 1] >= cache[i]
+    for (int i = 1, farest = 0; i < size; ++i) {
+        while (farest < size && farest + nums[farest] < i) {
+            ++farest;
         }
-        f[i]=f[idx]+1
+        // &#20551;&#35774;&#20320;&#24635;&#26159;&#21487;&#20197;&#21040;&#36798;&#25968;&#32452;&#30340;&#26368;&#21518;&#19968;&#20010;&#20301;&#32622;&#12290;
+        // &#21487;&#20197;&#35748;&#23450;farest + nums[farest]&#19968;&#23450;&#20250;&#22823;&#20110;i
+        cache[i] = cache[farest] + 1;
     }
-    return f[n-1]
+    return cache.back();
 }
-
 ```
 
 ### [palindrome-partitioning-ii](https://leetcode-cn.com/problems/palindrome-partitioning-ii/)
 
 > &#32473;&#23450;&#19968;&#20010;&#23383;&#31526;&#20018; _s_&#65292;&#23558; _s_ &#20998;&#21106;&#25104;&#19968;&#20123;&#23376;&#20018;&#65292;&#20351;&#27599;&#20010;&#23376;&#20018;&#37117;&#26159;&#22238;&#25991;&#20018;&#12290;
 > &#36820;&#22238;&#31526;&#21512;&#35201;&#27714;&#30340;&#26368;&#23569;&#20998;&#21106;&#27425;&#25968;&#12290;
 
-```go
-func minCut(s string) int {
-	// state: f[i] "&#21069;i"&#20010;&#23383;&#31526;&#32452;&#25104;&#30340;&#23376;&#23383;&#31526;&#20018;&#38656;&#35201;&#26368;&#23569;&#20960;&#27425;cut(&#20010;&#25968;-1&#20026;&#32034;&#24341;)
-	// function: f[i] = MIN{f[j]+1}, j < i && [j+1 ~ i]&#36825;&#19968;&#27573;&#26159;&#19968;&#20010;&#22238;&#25991;&#20018;
-	// intialize: f[i] = i - 1 (f[0] = -1)
-	// answer: f[s.length()]
-	if len(s) == 0 || len(s) == 1 {
-		return 0
-	}
-	f := make([]int, len(s)+1)
-	f[0] = -1
-	f[1] = 0
-	for i := 1; i <= len(s); i++ {
-		f[i] = i - 1
-		for j := 0; j < i; j++ {
-			if isPalindrome(s, j, i-1) {
-				f[i] = min(f[i], f[j]+1)
-			}
-		}
-	}
-	return f[len(s)]
-}
-func min(a, b int) int {
-	if a > b {
-		return b
-	}
-	return a
-}
-func isPalindrome(s string, i, j int) bool {
-	for i < j {
-		if s[i] != s[j] {
-			return false
-		}
-		i++
-		j--
-	}
-	return true
+```c++
+int minCut(string s) {
+    if (s.size() <= 1) {
+        return 0;
+    }
+    auto size = s.size();
+    vector<int> cache(size);
+    for (int i = 0; i < size; ++i) {
+        cache[i] = i;
+    }
+    vector<vector<bool>> isPalindrome(size, vector<bool>(size));
+    for (int right = 0; right < size; ++right) {
+        for (int left = 0; left <= right; ++left) {
+            // &#22914;&#26524;&#22836;&#23614;&#30456;&#21516;&#65292;&#21487;&#33021;&#20026;&#22238;&#25991;&#65281;
+            // len < 3&#26102;&#65292;&#30452;&#25509;&#21028;&#26029;&#20026;&#22238;&#25991;
+            // len >= 3&#26102;&#65292;&#21028;&#26029;&#37324;&#38754;&#19968;&#23618;&#65292;&#24038;&#21491;&#24448;&#37324;&#32553;&#19968;&#26684;
+            isPalindrome[left][right] = s[right] == s[left] && (right - left < 3 || isPalindrome[left + 1][right - 1]);
+        }
+    }
+    for (int i = 1; i < size; ++i) {
+        if (isPalindrome[0][i]) {
+            cache[i] = 0;
+            continue;
+        }
+        for (int j = 0; j < i; ++j) {
+            if (isPalindrome[j + 1][i]) {
+                cache[i] = min(cache[j] + 1, cache[i]);
+            }
+        }
+    }
+    return cache.back();
 }
 ```
 
