数据结构第二季 Day19 动态规划之最长公共子序列
2021-10-27 本文已影响0人
望穿秋水小作坊
1、最长公共子序列问题是什么问题？
image.png
2、最长公共子序列的动态规划三步曲？
- 思路启发：TMD 也太难了，这怎么想得到
- ①首先是二维数组，所以定义 dp[i][j]
- ②其次，从后往前面推（或者从前往后推），看看存在什么关系，从而搞出状态转移方程
image.png
3、上述思想的代码实现？
image.png
image.png
4、最长公共子序列-非递归实现？
image.png
5、如果要对上述代码进行空间优化要怎么做？
- 那必须分析 dp[i][j] 的使用过程
image.png
- 可以发现，dp 的分析，每一行的计算只依赖于上一行，所以可以使用滚动数组的方式进行优化。
6、基于上面的 dp 分析，每一行的计算只依赖于上一行，所以可以用滚动数组的思路进行优化？
image.png
7、上面是使用了 i <= 1的二维数组，其实可以优化到直接使用一维数组？
image.png
8、基于上一步的优化完毕，我们可以发现一维数组的话，还可以进行优化，将长度较短的作为一维数组，可以进一步节约空间
image.png
