如果仅需要求得最长公共子序列的代价，则最长公共子序列的空间复杂性可以降低到O(n)，其中n是两个序列中任意一个的长度
举一反三
- 使用动态规划算法求解最长公共子序列问题，引入数组c[i][j]存储序列x[1..i]和y[1..j]的最长公共子序列的长度，则对于长度为m和n的两条序列，其最长公共子序列的长度为c[m][n]。
- 字符序列abcde与字符序列abdge的最长公共子序列长度为()，最长公共子串长度为()。
- 使用动态规划算法求解最长公共子序列问题的时间复杂度为O(m+n)，其中m和n为两条序列的长度。
- 最长公共子序列问题中，如果采取穷举法，可以在序列A中子序列可能的开头和结尾（因为子序列由其开头位置和结尾位置唯一确定），然后在序列B中查找它是否存在，如果按照子序列长度降序枚举，找到的第一个公共子序列就是最长公共子序列。
- 在计算最长公共子序列的长度时，为了减少空间需求可以使用滚动数组。给定两个序列，长度分别为m和n，可以将短的序列作为行，长的序列作为列，最后可将空间需求减至O(min(m,n))。