把LIS和LCS对应的总共四种问题总结一下。
Longest Increasing Subsequce:
DP，复杂度O(n2)， 转移方程：
if (nums[j] < nums[i] ) dp[i] = max(dp[j] + 1, dp[i])Longest Increasing Subsubstring:
DP，纸上画个图可以发现，时间是O(n)，空间可以轮换。跟股票买卖有一题比较像。Longest Common Subsequence:
二维DP了，时间空间都是O(M*N)。方程：
- dp[i][j] = 0, if(i == 0) or (j == 0)
- dp[i][j] = dp[i-1][j-1] + 1, if(s[i] == t[j])
- dp[i][j] = max{dp[i][j-1] , dp[i-1][j] } , if(s[i] != t[j])
- Longest Common Substring:
与上面的类似，当str1[i] == str2[j]时，子序列长度veca[i][j] = veca[i - 1][j - 1] + 1；区别是当str1[i] ！= str2[j]时，veca[i][j]长度要为0，而不是max{veca[i - 1][j], veca[i][j - 1]}。
