动态规划求最长公共子序列
时间: 2023-11-17 12:01:49 浏览: 50
动态规划求最长公共子序列的过程如下:
1. 定义状态:设dp[i][j]为字符串X的前i个字符和字符串Y的前j个字符的最长公共子序列的长度。
2. 初始化状态:dp[j]和dp[i]均为0,因为其中一个字符串为空时,它们的最长公共子序列长度为0。
3. 状态转移方程:当X[i] == Y[j]时,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]即为字符串X和Y的最长公共子序列的长度,其中m和n分别为字符串X和Y的长度。
相关问题
C语言用动态规划求最长公共子序列
动态规划求最长公共子序列的思路如下:
首先,我们定义一个二维数组dp[m+1][n+1],其中m和n分别为两个字符串的长度加1。
接着,我们从两个字符串的第一个字符开始比较,依次填充dp数组。具体地,假设两个字符串分别为s1和s2,当前比较到的字符索引分别为i和j,则有以下三种情况:
1. 如果s1[i] == s2[j],那么这两个字符属于最长公共子序列中的一部分,因此dp[i][j] = dp[i-1][j-1] + 1。
2. 如果s1[i] != s2[j],那么这两个字符不可能同时出现在最长公共子序列中,因此我们需要从dp[i-1][j]和dp[i][j-1]中选取一个较大的值作为dp[i][j]的值。
3. 如果i或j等于0,说明有一个字符串已经比较完了,此时dp[i][j]的值为0。
最后,dp[m][n]就是最长公共子序列的长度。
下面是C语言实现代码:
```c
#include <stdio.h>
#include <string.h>
int max(int a, int b) {
return a > b ? a : b;
}
int lcs(char *s1, char *s2) {
int m = strlen(s1);
int n = strlen(s2);
int dp[m+1][n+1];
memset(dp, 0, sizeof(dp));
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][j-1], dp[i-1][j]);
}
}
}
return dp[m][n];
}
int main() {
char s1[] = "ABCD";
char s2[] = "BD";
printf("%d\n", lcs(s1, s2)); // 输出2
return 0;
}
```
动态规划求最长公共子序列算法设计
态规划求最长公共子序列算法设计如下:
1. 定义状态:设dp[i][j]为字符串A的前i个字符和字符串B的前j个字符的最长公共子序列长度。
2. 状态转移方程:当A[i] == B[j]时,dp[i][j] = dp[i-1][j-1] + 1;否则,dp[i][j] = max(dp[i-1][j], dp[i][j-1])。
3. 边界条件:dp[j] = dp[i] = 0。
4. 最终结果:dp[m][n],其中m和n分别为字符串A和B的长度。
下面是Python代码实现:
```python
def lcs(A, B):
m, n = len(A), len(B)
dp = [[0] * (n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if A[i-1] == B[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]
```
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_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)