数据结构第二季 Day19 动态规划之最长公共子序列

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