今天分享的题目是 LeetCode 上的第 1143 题最长公共子序列,难度是中等。解题的思路是动态规划(Dynamic Programing)。 动态规划的题解都是不好想到的,如果没有动态规划相关的的经验,基本上想不到这样的解题方法。我写这篇文章的意义,也就是将解这道题或者类似题目的动态规划的解题方法讲解清楚,为后续的发展打下基础。
给定两个字符串 text1 和 text2,返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ,返回 0 。
示例:
输入:text1 = "abcde", text2 = "ace" 输出:3 解释:最长公共子序列是 "ace" ,它的长度为 3 。
输入:text1 = "ABCBDAB", text2 = "BDCABA" 输出:4 解释:最长公共子序列是 "BDAB" ,它的长度为 4 。
意义:
如上图所示, dp(i, j)
表示的意义:是texts1 前 i 个元素
与texts2 前 j 个元素
的最长公共子序列长度。那么:
dp(i, 0)、dp(0, j)
初始值均为 0。 理解:这个很好理解,只要有 text1和 text2有一个是空串,它们的公共子序列的长度就为0dp(i, j) = dp(i – 1, j – 1) + 1
理解:如果 texts1[i-1] = texts2[j-1],它们的公共子序列的长度就是在dp(i-1, j-1)上加1texts1[i – 1] ≠ texts2[j – 1
],那么 dp(i, j) = max { dp(i – 1, j), dp(i, j – 1) }
理解:如果texts[i-1] != texts2[j-1],则其结果如下图所示的2种情况,我们只取最大的那个texts1 前 i-1 个元素
与texts2 前 j 个元素
的最长公共子序列长度texts1 前 i 个元素
与texts2 前 j-1 个元素
的最长公共子序列长度dp的意义: dp(i, j)
是【nums1 前 i 个元素
】与【nums2 前 j 个元素
】的最长公共子序列长度
dp(i, 0)、dp(0, j)
初始值均为 0nums1[i – 1] = nums2[j – 1]
,那么 dp(i, j) = dp(i – 1, j – 1) + 1
nums1[i – 1] ≠ nums2[j – 1]
,那么 dp(i, j) = max { dp(i – 1, j), dp(i, j – 1) }
dp[m+1][n+1]
的数组,即m+1
行n+1
列dp[m][n]
【因为2层for循环,可以把矩阵的每个位置的数据都算出来,然后找到最大值】
dp[i][0]
和dp[0][j]
的值肯定为0,因此没有交集func longestCommonSubsequence(_ text1: String, _ text2: String) -> Int {
if text1.count == 0 || text2.count == 0 { return 0 }
// 将字符串转成数组
var _text1 = Array(text1)
var _text2 = Array(text2)
// 创建 [m+1][n+1]的数组
var dp = [[Int]](repeating: [Int](repeating: 0, count: text2.count+1), count: text1.count+1)
for i in 1...text1.count {
for j in 1...text2.count {
// 这句是重点 [i-1]和[j-1],因为dp数组是m+1和n+1的,所以dp是可以从1开始的,但是texts数组是m的,是以0开始的。
if _text1[i-1] == _text2[j-1]
{
dp[i][j] = dp[i-1][j-1] + 1
}else {
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
}
}
}
// 2层for循环,会将数组里面的每个地方的值都算出来
return dp[text1.count][text2.count]
}
今天比较详细的讲解了一道关于动态规划的问题。关于这种定义二维数组来解题的方式,其实在很多地方都会用到,希望这种思路,以及里面的实现细节能给大家带来启发。
end