动态规划方法求解最长公共子序列问题思路
时间: 2023-07-08 15:10:04 浏览: 50
最长公共子序列问题是求两个字符串中最长的相同子序列的长度,可以用动态规划方法求解。
具体思路如下:
1. 定义状态:设字符串A和B的长度分别为m和n,用dp[i][j]表示A的前i个字符和B的前j个字符的最长公共子序列长度。
2. 初始化状态:dp[0][0]=0,dp[0][j]=0,dp[i][0]=0,表示空字符串与任何字符串的最长公共子序列长度都为0。
3. 状态转移方程:当A[i]=B[j]时,dp[i][j] = dp[i-1][j-1]+1,表示当前字符相等时,最长公共子序列长度加1;当A[i]!=B[j]时,dp[i][j] = max(dp[i-1][j], dp[i][j-1]),表示当前字符不相等时,最长公共子序列的长度为A的前i-1个字符和B的前j个字符的最长公共子序列长度和A的前i个字符和B的前j-1个字符的最长公共子序列长度中的较大值。
4. 最终结果:dp[m][n]就是A和B的最长公共子序列的长度。
时间复杂度为O(mn),空间复杂度为O(mn)。
相关问题
动态规划算法求解最长公共子序列问题c++
最长公共子序列问题可以使用动态规划算法求解。
具体的思路是,定义一个二维数组dp[i][j],表示字符串1的前i个字符与字符串2的前j个字符的最长公共子序列长度。则有以下动态转移方程:
- 当s1[i] == s2[j]时,dp[i][j] = dp[i-1][j-1] + 1;
- 当s1[i] != s2[j]时,dp[i][j] = max(dp[i-1][j], dp[i][j-1])。
最终的结果为dp[m][n],其中m和n分别为字符串1和字符串2的长度。
以下是C++代码实现:
```
int lcs(string s1, string s2) {
int m = s1.length();
int n = s2.length();
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
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]);
}
}
}
return dp[m][n];
}
```
动态规划法求解最长公共子序列问题的c++算法实现
下面是使用动态规划法求解最长公共子序列问题的c++算法实现:
```c++
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int main()
{
string str1, str2;
cin >> str1 >> str2;
int len1 = str1.length(), len2 = str2.length();
int dp[len1 + 1][len2 + 1]; // 定义dp数组
for (int i = 0; i <= len1; i++) {
dp[i][0] = 0;
}
for (int j = 0; j <= len2; j++) {
dp[0][j] = 0;
}
for (int i = 1; i <= len1; i++) {
for (int j = 1; j <= len2; j++) {
if (str1[i - 1] == str2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1; // 相同则加1
}
else {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); // 不同则取左、上两个状态的较大值
}
}
}
cout << dp[len1][len2] << endl; // 输出最长公共子序列长度
return 0;
}
```
算法思路:
我们定义 $dp[i][j]$ 表示字符串 $str1$ 的前 $i$ 个字符和字符串 $str2$ 的前 $j$ 个字符的最长公共子序列长度。初始化时,$dp$ 数组的第一行和第一列都为 $0$,因为其中一个字符串为空字符串时,它的最长公共子序列长度一定为 $0$。接着,我们从字符串 $str1$ 的第 $1$ 个字符和字符串 $str2$ 的第 $1$ 个字符开始遍历,如果这两个字符相等,那么此时的最长公共子序列长度就应该是 $dp[i-1][j-1]+1$;如果这两个字符不相等,那么此时的最长公共子序列长度就应该是 $dp[i-1][j]$ 和 $dp[i][j-1]$ 中较大的那一个。最后,$dp[len1][len2]$ 即为所求的最长公共子序列长度。
算法复杂度:
该算法的时间复杂度为 $O(mn)$,其中 $m$ 为字符串 $str1$ 的长度,$n$ 为字符串 $str2$ 的长度。空间复杂度为 $O(mn)$。