动态规划最长公共子序列C++
时间: 2023-09-01 11:10:49 浏览: 48
下面是C++实现的最长公共子序列问题的动态规划算法:
```c++
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1010;
char s1[N], s2[N];
int f[N][N];
int main()
{
cin >> s1 >> s2;
int len1 = strlen(s1), len2 = strlen(s2);
for (int i = 1; i <= len1; i++)
for (int j = 1; j <= len2; j++)
{
f[i][j] = max(f[i - 1][j], f[i][j - 1]);
if (s1[i - 1] == s2[j - 1])
f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
}
cout << f[len1][len2] << endl;
return 0;
}
```
其中,$f[i][j]$ 表示 $s1$ 的前 $i$ 个字符和 $s2$ 的前 $j$ 个字符的最长公共子序列长度。
状态转移方程为:
$$f[i][j] = \begin{cases}0&i=0 \text{ or } j=0\\ f[i-1][j-1]+1&s1_i=s2_j\\ \max(f[i-1][j], f[i][j-1])&s1_i\neq s2_j\end{cases}$$
其中,第一行和第一列需要初始化为0,因为如果其中一个字符串为空,则最长公共子序列长度为0。最终答案即为 $f[len1][len2]$,其中 $len1$ 和 $len2$ 分别为两个字符串的长度。