当前位置：首页 > article >正文

算法刷题Day27:BM65 最长公共子序列(二)

article 2025/1/27 4:02:33

题目链接，点击跳转

题目描述：

在这里插入图片描述

考点：动态规划 回溯

解题思路：

动态规划是解决LCS问题的常用方法。其核心思想是将问题分解为子问题，并通过存储子问题的解来避免重复计算。

1. 定义dp数组元素含义

使用二维dp数组，元素dp[i][j]表示s2的前i个字符和s1的前j个字符的最长公共子序列长度。

2.dp数组状态转移方程

如果 s2[i-1] == s1[j-1]，则 dp[i][j] = dp[i-1][j-1] + 1。(来自左上角)
否则，dp[i][j] = max(dp[i][j-1], dp[i-1][j])。（来自正上方还是正左边）

3.dp数组初始化

dp长度声明的时候是字符串长度+1。
dp[0][j] = 0 和 dp[i][0] = 0。为了方便第一个字符的状态转移统一操作（相当于加了一个头节点）。
```
len1 = len(s1)
len2 = len(s2)
dp = [[0 for _ in range(len1+1)] for _ in range(len2+1)] # 字符串长度+1
```
回溯法寻找LCS
在动态规划的基础上，我们可以使用回溯法来找到具体的LCS。回溯法通过反向追踪 used数组，逐
步构建出LCS。

used数组用来记录当前used[i][j]元素是从左上角or正左边or正上方来的，记为1 or 2 or 3。

1. 回溯结束条件：

当到达字符串边界，即i==0 or j==0 的时候说明找到一个LCS。

2. 回溯体

当used[i][j] == 1时说明从左上角来，继续回溯 (i-1，j-1)。
当used[i][j] == 2时说明从正左边来，继续回溯 (i，j-1)。
当used[i][j] == 3时说明从正上方来，继续回溯 (i-1，j)。

s1=abc, s2=adc 的dp数组和used数据状态转移示例图

s1=abc, s2=adc 示例图

代码：

class Solution:
    def LCS(self , s1: str, s2: str) -> str:
        len1 = len(s1)
        len2 = len(s2)
        dp = [[0 for _ in range(len1+1)] for _ in range(len2+1)]
        used = [[0 for _ in range(len1+1)] for _ in range(len2+1)]
        for i in range(1,len2+1):
            for j in range(1,len1+1):
                if s1[j-1] == s2[i-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                    used[i][j] = 1
                    continue                   # 忽略以下继续下一个循环
                elif dp[i][j-1] >= dp[i-1][j]: # 左 > 上
                    dp[i][j] = dp[i][j-1]
                    used[i][j] = 2
                    continue
                else:                          # 上 > 左
                    dp[i][j] = dp[i-1][j]
                    used[i][j] = 3         
        # 使用回溯法寻找路径
        result = []
        def backtrack(i,j,path):
            # 结束条件：到边节点
            if i==0 or j==0:
                result.append(path[::-1])
                return
            if used[i][j] == 1:
                backtrack(i-1,j-1, path+s2[i-1])
            elif used[i][j] == 2:
                backtrack(i,j-1, path)
            elif used[i][j] == 3:
                backtrack(i-1,j,path)
        backtrack(len2,len1,'')
        if result == [] or result[0] == '':
            return '-1'
        else:
            return result[0]