1143. Longest Common Subsequence
給你兩個字串求出它們的最長共通子序列長。
Example：
Input: text1 = "abcde", text2 = "ace"
Output: 3
Explanation: The longest common subsequence is "ace" and its length is 3.
思路：
1.這題是演算法課程有教dp都會提到的經典題目，大多子字串問題也多是用dp解。
2.先定義dp，dp[i][j] 表示s1長度為i 且 s2長度為j時的最長子序列長度，所以我們
宣告一個大小為dp[m+1][n+1]的陣列（因為要包含長度為0的case）
3.再來我們需要找出狀態轉移方程式，字串s1和s2的最後一個元素分別以e1與e2
表示，剩餘部分以 sub1 與 sub2表示，故可以將其如下表示：
s1 = sub1 + e1
s2 = sub2 + e2
可以分成四個情形討論：
LCS包含e1不包含e2
LCS(s1,s2) = LCS(s1,sub2) // 捨棄右邊
LCS包含e2不包含e1
LCS(s1,s2) = LCS(sub1,s2) // 捨棄左邊
LCS包含e1且包含e2
LCS(s1,s2) = LCS(sub1,sub2) + 1 // 全捨棄且序列長度加一
LCS不包含e1且不包含e2
LCS(s1,s2) = LCS(sub1,sub2) // 全捨棄
上述四個式子可以結論如下：
LCS(s1,s2) = max(LCS(s1,sub2), LCS(sub1,s2), LCS(sub1,sub2)) when e1 ≠ e2
LCS(sub1, sub2) + 1 when e1 == e2
因為都不取一定比只取一個小，所以全捨棄的case可以無視，有了遞迴關係式就可以
改寫成迭代，表示如下：
dp[i][j] = dp[i-1][j-1] when s[i]==s[j]
max(dp[i-1][j], dp[i][j-1]) when s[i]!=s[j]
Java Code：

大師

看到題目就想到 DP 了 .. 可是我還是不會

樹樹來看這個== https://youtu.be/FLbqgyJ-70I

大師

大師