reference： nine chapter algrithm
本篇給出一道單序列動態規劃題解的詳細分析過程，再給一道雙序列型動態規劃，最後留一道思考題。
Word Break
Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
Note:
Example 1:
Input: s = "leetcode", wordDict = ["leet", "code"]Output: trueExplanation: Return true because "leetcode" can be segmented as "leet code".
Example 2:
Input: s = "applepenapple", wordDict = ["apple", "pen"]Output: trueExplanation: Return true because "applepenapple" can be segmented as "apple pen apple".
Note that you are allowed to reuse a dictionary word.
Example 3:
Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]Output: false
上述題意是給定一個字符串，能否被切割成給成一個或者多個單詞，且單詞必須是給定的字典中的詞。
數學歸納法思路分解：
#1 給定字符串 s ="xxxxxxixxxxxxxxxx"; 如何判定 s.charAt(0) 至s.charAt(i)的子字符串能不能被完美切割？
#2 考慮一種最簡單情況： 假定0 到 i 的子字符串能被切割成兩個單詞，那麼該字符串就能被完美切割。
#3 如何找到切割點呢？從0到i一次遍歷即可。
找到一個j, 滿足 0 < j < i , 只要s.substring(1,j) 和 s.substring(j+1,i) 兩個子字符串在給定的詞典中，那麼該字符串就能完美切割。
上述計算過程，我們用一個boolean型一維數組f[s.length() + 1]來記錄計算過程中的結果。
f[i] = true表示從0到i的子字符串能被完美切割,否則 f[i] = false。
#4 以上述例子開始推導 "leetcode", wordDict = ["leet", "code"]
boolean f[] = new boolean[9]; f[0] = true 表示空字符能被完美切割。
從左往右開始推導。
子字符串 substring(1,1) = "l", 不在詞典中，f[1] = false;
子字符串 substring(1,2) = "le", 判斷兩種情況：
（1） 分別判斷「l」和「e」是否在詞典中
（2）判斷"le"是否在詞典中
上述都不在，所以f[2] = false
子字符串 substring(1,3) = "lee", 下列情況：
（1） 「l」，「ee」都不在字典中
（2）「le」，「e」都不在字典中
（3） 「lee」 不在字典中
f[3] = false;
子字符串 substring(1,4) = "leet", 下列情況：
（1） 「l」，「ee」都不在字典中
（2）「le」，「e」都不在字典中
（3） 「lee」,"t" 都不在字典中
(4) 「leet」 在字典中，所以f[4] = true;
依次類推即可。 上述過程因為已經把部分計算子結構放在了boolean數組中，避免了重複計算，因此是個典型的動態規劃。抽象如下：
以下筆者的解法在leetcode上的運行時間是4毫秒，擊敗91.33%的submission。
Runtime: 4 ms, faster than 91.33% of Java online submissions for Word Break.
class Solution {public boolean wordBreak(String s, List<String> wordDict) { if(s == null || s.length() < 1) { return true; }
int length = s.length(); boolean[] f = new boolean[length + 1]; f[0] = true;
for(int i = 1; i <= length; i++) { for(int j = 0; j < i; j++) { String sb = s.substring(j, i); if(f[j] == true) { if(wordDict.contains(sb)) { f[i] = true; break; } } } }
return f[length]; }
}再來一個雙序列動態規划算法
Given two strings, find the longest common subsequence (LCS).
Your code should return the length of LCS.
Example 1: Input: "ABCD" and "EDCA" Output: 1 Explanation: LCS is 'A' or 'D' or 'C'Example 2: Input: "ABCD" and "EACB" Output: 2 Explanation: LCS is "AC"
問題描述：字符序列的子序列是指從給定字符序列中隨意地（不一定連續）去掉若干個字符（可能一個也不去掉）後所形成的字符序列。令給定的字符序列X=「x0，x1，…，xm-1」，序列Y=「y0，y1，…，yk-1」是X的子序列，存在X的一個嚴格遞增下標序列<i0，i1，…，ik-1>，使得對所有的j=0，1，…，k-1，有xij=yj。例如，X=「ABCBDAB」，Y=「BCDB」是X的一個子序列。（來源：百度）
雙序列動態規劃思考模版
state: f[i][j]代表了第一個sequence的前i個數字/字符，配上第二個sequence 的前j個...
function: f[i][j] = 研究第i個和第j個的匹配關係
initialize: f[i][0] 和 f[0][i]
answer: f[n][m] n = s1.length() m = s2.length()
Longest Common Subsequence 模版
state: f[i][j]表示前i個字符配上前j個字符的LCS的長度
function: f[i][j] = MAX(f[i-1][j], f[i][j-1], f[i-1][j-1] + 1) // A[i - 1] == B[j - 1]
= MAX(f[i-1][j], f[i][j-1])
intialize: f[i][0] = 0 f[0][j] = 0
answer: f[n][m]
此算法的推導過程與之前的編輯距離思路一致，請查看本公眾號（搜索：超級碼厲）的歷史文章。
java實現：
public class LCS { public int lcs(String str1, String str2) { if(str1 == null || str2 == null || str1.length() == 0 || str2.length() == 0) { return 0; } int lengthOfS1 = str1.length(); int lengthOfS2 = str2.length(); int[][] f = new int[lengthOfS1 + 1][lengthOfS1 + 1];
for(int i = 0; i <= lengthOfS1; i++) for(int j = 0; j <= lengthOfS2;j++) { if(i == 0 || j == 0) { f[i][j] = 0; } else if(str1.charAt(i-1) == str2.charAt(j-1)) { f[i][j] = f[i-1][j-1] + 1; } else { f[i][j] = Math.max(f[i][j-1],f[i-1][j]); } } return f[lengthOfS1][lengthOfS2]; }
}類似的題：
Interleaving String，
Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
For example,
Given:
s1 = "aabcc",
s2 = "dbbca",
When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.
請朋友們思考，先給出解題模版：
(f[i][j-1] && (s2[j-1]==s3[i+j-1])
initialize: f[i][0] = (s1[0..i-1] == s3[0..i-1])
f[0][j] = (s2[0..j-1] == s3[0..j-1])
answer: f[n][m], n = sizeof(s1), m = sizeof(s2)
今天把單序列與雙序列典型題目給了模版及題解，朋友是否理解了動態規劃思想呢？
接下來，背包型等動態規劃陸續分享。請關注公眾號： 超級碼厲。