动态规划实现最长公共子序列c++代码
时间: 2024-05-16 15:11:09 浏览: 19
动态规划是一种常用的算法思想,用于解决一些优化问题。最长公共子序列问题就是其中一个典型的例子。以下是实现最长公共子序列的c++代码:
```
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1010;
int dp[N][N];
int main()
{
string s1, s2;
cin >> s1 >> s2;
int n1 = s1.size(), n2 = s2.size();
for (int i = 1; i <= n1; i++)
for (int j = 1; j <= n2; 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]);
}
cout << dp[n1][n2] << endl;
return 0;
}
```
这段代码首先读入两个字符串s1和s2,并定义dp数组表示最长公共子序列的长度。接着,双重循环遍历s1和s2中的每个字符,并根据状态转移方程进行动态规划,最后输出dp[n1][n2]即可。
相关问题
用动态规划法最长公共子序列c++代码
下面是用动态规划法求解最长公共子序列的C++代码:
```c++
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=1005;
int dp[maxn][maxn];
int main(){
string s1,s2;
cin>>s1>>s2;
int len1=s1.length(),len2=s2.length();
for(int i=1;i<=len1;i++){
for(int j=1;j<=len2;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]);
}
}
cout<<dp[len1][len2]<<endl;
return 0;
}
```
该代码中,我们使用一个二维数组`dp[i][j]`来表示s1的前i个字符和s2的前j个字符的最长公共子序列的长度。具体的状态转移方程如下:
```c++
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]);
```
如果s1[i-1]和s2[j-1]相等,那么最长公共子序列就是s1的前i-1个字符和s2的前j-1个字符的最长公共子序列加上这两个字符。否则,最长公共子序列就是s1的前i-1个字符和s2的前j个字符的最长公共子序列,或者是s1的前i个字符和s2的前j-1个字符的最长公共子序列,取其中的较大值即可。最终,`dp[len1][len2]`就是s1和s2的最长公共子序列的长度。
动态规划法实现最长公共子序列c++
动态规划法实现最长公共子序列是一种常见的算法,它可以用来解决两个序列之间的最长公共子序列问题。具体实现过程如下:
1. 定义一个二维数组dp,其中dp[i][j]表示序列1的前i个元素和序列2的前j个元素的最长公共子序列的长度。
2. 初始化dp数组,将dp[j]和dp[i]都设为0。
3. 遍历序列1和序列2,如果当前元素相同,则dp[i][j] = dp[i-1][j-1] + 1;否则,dp[i][j] = max(dp[i-1][j], dp[i][j-1])。
4. 最终dp[m][n]即为序列1和序列2的最长公共子序列的长度。
以下是C++代码实现:
```
int longestCommonSubsequence(string text1, string text2) {
int m = text1.size(), n = text2.size();
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 (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]);
}
}
}
return dp[m][n];
}
```
相关推荐
![txt](https://img-home.csdnimg.cn/images/20210720083642.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)