【LeetCode】1143.最长公共子序列（闫氏dp可视化无分析）

**最长公共子序列**

**问题描述**

给定两个字符串 `s1` 和 `s2`,找到它们的最长公共子序列（LCS）。最长公共子序列是指两个字符串中共同出现的最大子串。

**示例**

* 输入:`s1 = "AGGTAB"、`$s2 = "GXTXAYB"`，输出： `"GTAB"`
* 输入:`s1 = "ABC"、`$s2 = "DEF"`，输出： `""`

**闫氏dp可视化**

首先，我们需要理解闫氏dp的概念。闫氏dp是一种动态规划的方法，它通过递归地计算子问题来求解原问题。

在本题中，我们可以将两个字符串 `s1` 和 `s2` 分别视为两个序列。我们希望找到这两个序列之间的最长公共子序列。

我们定义一个二维数组 `dp`，其中 `dp[i][j]` 表示 `s1[0..i-1]` 和 `s2[0..j-1]` 的最长公共子序列的长度。

**代码**

def longestCommonSubsequence(s1, s2):
 m = len(s1)
 n = len(s2)

 # 初始化dp数组 dp = [[0 for _ in range(n +1)] for _ in range(m +1)]

 # 填充dp数组 for i in range(1, m +1):
 for j in range(1, n +1):
 if s1[i -1] == s2[j -1]:
 dp[i][j] = dp[i -1][j -1] +1 else:
 dp[i][j] = max(dp[i -1][j], dp[i][j -1])

 # 回溯求解最长公共子序列 lcs = []
 i, j = m, n while i >0 and j >0:
 if s1[i -1] == s2[j -1]:
 lcs.append(s1[i -1])
 i -=1 j -=1 elif dp[i -1][j] > dp[i][j -1]:
 i -=1 else:
 j -=1 # 返回最长公共子序列 return "".join(reversed(lcs))

**注释**

* `dp` 数组的初始化：我们将 `dp` 初始化为一个二维数组，大小为 `(m +1) x (n +1)`，其中 `m` 和 `n` 分别是两个字符串 `s1` 和 `s2` 的长度。
* 填充 `dp` 数组：我们通过递归地计算子问题来填充 `dp` 数组。具体来说，我们检查 `s1[i -1]` 是否等于 `s2[j -1]`，如果相等，则 `dp[i][j] = dp[i -1][j -1] +1`；否则，`dp[i][j] = max(dp[i -1][j], dp[i][j -1])`。
* 回溯求解最长公共子序列：我们从 `dp[m][n]` 开始，依次回溯到 `dp[0][0]`。如果 `s1[i -1] == s2[j -1]`，则将 `s1[i -1]` 添加到最长公共子序列中，并且 `i -=1` 和 `j -=1`；否则，如果 `dp[i -1][j] > dp[i][j -1]`，则 `i -=1`；否则，则 `j -=1`。
* 返回最长公共子序列：我们将回溯求解的最长公共子序列反转后返回。

**时间复杂度**

* 初始化 `dp` 数组：O(m * n)
* 填充 `dp` 数组：O(m * n)
* 回溯求解最长公共子序列：O(m + n)

总的来说，时间复杂度为 O(m * n)。

**空间复杂度**

* 初始化 `dp` 数组：O(m * n)

空间复杂度为 O(m * n)。