add palindrome partition ii

tg123 · tg123 · commit f2f4e03adb37 · 2014-08-22T20:14:10.000+08:00
diff --git a/palindrome-partitioning-ii/README.md b/palindrome-partitioning-ii/README.md
@@ -1,4 +1,16 @@
+## [Longest Palindromic Substring](../longest-palindromic-substring) + [Word Break](../word-break)
 
-## TODO 
-  * write down thinking
+After running [Longest Palindromic Substring](../longest-palindromic-substring), 
+we got a table `P[len][index]`, that is, we can tell if `s[i..j]` is palindromic
 
+## Apply [Word Break](../word-break)
+
+`M[i]` means the mincut of `s[0..i]`.
+
+When a new char comes, we have 3 choices:
+ 
+ * `M[i + 1] = 0`: if `s[0..i + 1]` is palindromic
+ * `M[i + 1] = M[i] + 1`: cut at `i`, between the old string `s[0..i]` and the new char.
+ * `M[i + 1] = M[j] + 1`: cut at `j`, `j from 0 -> i`, such that `s[j..i+1]` is palindromic, between the `s[0..j]` and `s[j..i + 1]`.
+
+Our job is to find the minimum value among them.
