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：