算法-子序列问题

子序列问题

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

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

"abcd"

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

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

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

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

一维dp数组

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

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

给作者买杯咖啡吧~~~