题目描述
给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0。 一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。 例如，"ace" 是 "abcde" 的一个子序列，但 "aec" 不是 "abcde" 的一个子序列。
思路
本题是典型的动态规划问题，主要思路是使用二维数组dp，这里记录一下思考过程：
首先我们可以从后往前推导，最长的公共子序列其实是一个累积的过程，我们先想象有一个函数super可以计算出两个字符串的组最长公共子序列
这里有两种情况：
- text1和text2的最后一个字符相等，都为 e，那么可以得到：
super('ace', 'abcde') = super('ac', 'abcd') + 1- text1和text2的最后一个字符不相等，那么要么是text1继续向前找，要么是text2继续向前找，我们又是需要「最大」，那么可以得到：
super('abc', 'abd') = max(super('ab', 'abd'), super('abc', 'ab'))按照上面的逻辑，其实这就是一个递归过程。但是，一直切字符串太消耗内存了。 聪明一点的做法是：我们不传字符串，我们传索引（长度）。 设 i 是 text1 正在考察的长度，j 是 text2 正在考察的长度。 我们把上面的函数改写成 super(i, j)，意思是：text1 的前 i 个字符和 text2 的前 j 个字符的匹配结果。 自然而然就想到了二维数组。 （鼓掌！）
因此，我们就可以得到动态规划的「状态转移方程」
dp[i][j] = dp[i-1][j-1] + 1
dp[i][j] = max(dp[i-1][j], dp[i][j-1])涉及方法
- 动态规划 动态规划的核心是找到「状态转移方程」
- 二维数组 二维数组的使用可以让我们在计算过程中存储中间结果，避免重复计算，提高效率。
// 初始化一个 m x n 的二维数组
const dp = new Array(m).fill(0).map(() => new Array(n).fill(0))
// 或者使用 Array.from
const dp = Array.from({ length: m }, () => new Array(n).fill(0));关于Array.from的使用，可以参考 MDN 上的文档：https://developer.mozilla.org/zh-CN/docs/Web/JavaScript/Reference/Global_Objects/Array/from
踩坑 “为什么不用 new Array(m).fill(new Array(n).fill(0)) ？” 因为 JavaScript 中的数组是引用类型。如果给 fill 传入一个数组实例，外层数组的所有项都会指向这个相同的内存地址。 修改其中一行的数据，其他行也会跟着改变，导致状态污染。所以我使用 Array.from 结合回调函数，确保每一行都是每次执行回调时 new 出来的独立数组实例。
实际处理
在实际的代码实现中，我们需要注意边界条件的处理，例如当 i 或 j 为 0 时，dp[i][j] 应该为 0，因为空字符串与任何字符串的最长公共子序列长度都是 0。
避免我们的字符串1和字符串2的长度为0或者首个字符相同的时候，访问dp[-1][-1]导致数组越界或者错误的结果。
因此我们这里需要给二维数组加一个边框：
const m = text1.length, n = text2.length
const dp = Array(m + 1).fill(0).map(() => Array(n + 1).fill(0))ps:说好的算法日记，结果隔好久才写，忏悔忏悔。马上自律起来