LIS(Substring & subsequence)

把LIS和LCS对应的总共四种问题总结一下。

1. Longest Increasing Subsequce:
   DP，复杂度O(n²)， 转移方程：
   if (nums[j] < nums[i] ) dp[i] = max(dp[j] + 1, dp[i])

2. Longest Increasing Subsubstring:
   DP，纸上画个图可以发现，时间是O(n)，空间可以轮换。跟股票买卖有一题比较像。

3. 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])

4. 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]}。