动态规划系列（二）

动态规划系列（二）
4、最长公共子序列
最长公共子序列（Longest Common Subsequence, 简称 LCS）是一道非常经典的二维动态规划，也是一道非常经典的面试题目。
最长公共子序列 问题就是让我们求两个字符串的 LCS 长度。比如输入 str1 = “abcde” , str2 = “aceb”, 算法应该输出3，因为 str1 和 str2 的最长公共子序列是 “ace", 它的长度是3。
分析：
第一步，一定要明确 dp 数组的含义 对于两个字符串的动态规划问题，套路是通用的，一般都需要一个二维 dp 数组。 其中， dp[i][j] 的含义是：对于 s1[0…i-1] 和 s2[0,…j-1]， 它们的 LCS 长度是 dp[i][j]。
第二步，定义 base case 专门让索引为 0 的行和列表示空串，dp[0][…] 和 dp[…][0] 都应该初始化为 0。
第三

动态规划系列（二）最先出现在Python成神之路。