最长公共子序列
这是leetcode上的一道原题 题目连接如下
题目描述如下
给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
- 例如，“ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
递归版本
还是一样 我们首先来设计一个函数 函数原型如下
int process(string& str1 , string& str2 , int i , int j)
这个递归函数的含义是 给你两个字符串 s1 和 s2 再给你它们的一个最大下标 现在要求这个函数返回它们公共子序列的最大值
参数表示如下
- int i ： 表示一个字符串str1中的下标
- int j ： 表示一个字符串str2中的下标
还是一样 我们首先想base case
- 假如i的下标为0 j的下标也为0 此时我们就可以直接返回一个确定的值
代码表示如下
// base case if (i == 0 && j == 0) { return str1[i] == str2[j] ? 1 : 0; }
此时我们排除了i 和 j都为0的情况 剩下了三种情况
- i j 其中一个为0 （两种）
- i j都不为0
当i j都不为0时候 我们还要讨论 i j 是否为公共子序列的下标也是分为三种情况
- i可能是 j不是
- j可能是 i不是
- i j都是
之后我们分别将代码全部写好就可以了
if (i == 0) { if (str1[i] == str2[j]) { return 1; } else { return process(str1 , str2 , i , j-1); } } else if (j == 0) { if (str1[i] == str2[j]) { return 1; } else { return process(str1 , str2 , i - 1 , j); } } else { // j != 0; // i != 0; // possible i ... j int p1 = process(str1 , str2 , i - 1 , j); int p2 = process(str1 , str2 , i , j - 1); int p3 = str1[i] == str2[j] ? 1 + process(str1 , str2 , i -1 , j -1) : 0 ; return max(p1 , max (p2 , p3)); } }
动态规划
我们观察原递归函数
process(string& str1 , string& str2 , int i , int j)
我们发现变化的值只有 i 和 j
于是我们可以利用i j 做出一张dp表
还是一样 我们首先来看base case
// base case if (i == 0 && j == 0) { return str1[i] == str2[j] ? 1 : 0; }
于是我们就可以把i == 0 并且 j ==0 的这些位置值填好
dp[0][0] = str1[0] == str2[0] ? 1 : 0;
之后根据 i == 0 j ==0 这两个分支继续动规
for (int j = 1 ; j < static_cast<int>(str2.size()) ; j++) { dp[0][j] = str1[0] == str2[j] ? 1 : dp[0][j-1]; } for (int i = 1 ; i < static_cast<int>(str1.size()) ; i++) { dp[i][0] = str1[i] == str2[0] ? 1 : dp[i-1][0]; }
递归的最后一部分依赖三个位置
else { // j != 0; // i != 0; // possible i ... j int p1 = process(str1 , str2 , i - 1 , j); int p2 = process(str1 , str2 , i , j - 1); int p3 = str1[i] == str2[j] ? 1 + process(str1 , str2 , i -1 , j -1) : 0 ; return max(p1 , max (p2 , p3)); }
我们只需要再递归表中依次填写即可 代码表示如下
int process1(string& str1, string& str2, vector<vector<int>>& dp) { dp[0][0] = str1[0] == str2[0] ? 1 : 0; for (int j = 1 ; j < static_cast<int>(str2.size()) ; j++) { dp[0][j] = str1[0] == str2[j] ? 1 : dp[0][j-1]; } for (int i = 1 ; i < static_cast<int>(str1.size()) ; i++) { dp[i][0] = str1[i] == str2[0] ? 1 : dp[i-1][0]; } for (int i = 1 ; i < static_cast<int>(str1.size()) ; i++) { for (int j = 1 ; j < static_cast<int>(str2.size()) ; j++) { int p1 = dp[i-1][j]; int p2 = dp[i][j-1]; int p3 = str1[i] == str2[j] ? 1 + dp[i-1][j-1] : 0; dp[i][j] = max(p1 , max(p2 , p3)); } } return dp[str1.size() - 1][str2.size() - 1]; }
