算法-子序列问题

子序列问题

子序列问题是很常见的一类问题，与之类似的还有子串问题，这两者有什么区别呢？

子序列是不需要连续的，但是字串是需要连续的。

"abcd"

子序列是["a","b","c","d","ab","ac","ad","bc","bd","cd"]

字串是["a","b","c","d","ab","bc","cd"]

观察一下两者之间的区别。

这类子序列问题一般使用动态规划来做，一般有以下两种思路

一维dp数组

# int[] dp = new int[str.length()];
dp[i]的意思是在字符串str[0,i]中，以str[i]结尾的目标子序列的长度是dp[i]

栗题：力扣300最长递增子序列