定义
根据 Leetcode 的习惯,子序列(subsequence)不必连续,子数组(subarray)或子字符串(substring)必须连续。
动态规划中,子串子序列的问题大概分为如下几种:
单条数组(字符)内部的对比,比如:
- 5. 最长回文子串 + 516. 最长回文子序列
- 300. 最长递增子序列 + 674. 最长连续递增序列(不使用动态规划反而更简单一些)
两条数组(字符)之间做对比,比如
- 1143. 最长公共子序列 和 最长公共子串 (leetcode 上没有这个题,随便找了一个)
- 72. 编辑距离