长公共子序列长度 分数 15 作者 王东 单位 贵州师范学院 求两个字符串的最长公共子序列长度。 输入格式: 输入长度≤100的两个字符串。 输出格式: 输出两个字符串的最长公共子序列长度。
时间: 2024-04-05 14:29:35 浏览: 56
这是一个经典的动态规划问题。设dp[i][j]表示字符串A的前i个字符和字符串B的前j个字符的最长公共子序列长度。状态转移方程为:
如果A[i] == B[j],则dp[i][j] = dp[i-1][j-1] + 1;
如果A[i] != B[j],则dp[i][j] = max(dp[i-1][j], dp[i][j-1])。
其中,如果A[i] == B[j],说明A[i]和B[j]可以加入到当前的最长公共子序列中,它们对应的最长公共子序列长度为dp[i-1][j-1]+1;如果A[i] != B[j],则说明A[i]和B[j]不能同时包含在当前的最长公共子序列中,此时需要分别考虑A[i]和B[j]是否可以加入到当前的最长公共子序列中,取两者的最大值。
最终的结果为dp[m][n],其中m和n分别为字符串A和字符串B的长度。
下面是一份参考代码实现:
相关问题
C++实现长公共子序列长度 分数 15 作者 王东 单位 贵州师范学院 求两个字符串的最长公共子序列长度。 输入格式: 输入长度≤100的两个字符串。 输出格式: 输出两个字符串的最长公共子序列长度。
下面是C++的参考代码实现:
```cpp
#include <iostream>
#include <cstring>
using namespace std;
const int N = 110;
int dp[N][N];
int main()
{
string A, B;
cin >> A >> B;
int m = A.size(), n = B.size();
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
{
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]);
}
cout << dp[m][n] << endl;
return 0;
}
```
其中,使用dp[i][j]表示字符串A的前i个字符和字符串B的前j个字符的最长公共子序列长度。对于状态转移方程,需要特别注意字符串下标从0开始,因此需要将i和j减1。
6-6 判断两棵二叉树是否同构(递归法) 分数 10 作者 王东 单位 贵州师范学院 判断
好的,你的问题是如何判断两棵二叉树是否同构(递归法)。
同构指的是两棵二叉树的结构相同,但是节点的值可以不同。这里给出递归法的代码实现:
```python
def is_isomorphic(root1, root2):
if not root1 and not root2:
return True
if not root1 or not root2:
return False
if root1.val != root2.val:
return False
return (is_isomorphic(root1.left, root2.left) and
is_isomorphic(root1.right, root2.right)) or \
(is_isomorphic(root1.left, root2.right) and
is_isomorphic(root1.right, root2.left))
```
在递归过程中,首先判断两个根节点是否为空,如果都为空,则返回 True。如果其中一个为空,则返回 False。接下来判断两个根节点的值是否相同,如果不相同,则返回 False。
如果两个根节点的值相同,那么就需要递归判断左子树和右子树是否同构,或者判断左子树和右子树是否交叉同构。只有两者之一成立,才返回 True,否则返回 False。
这样,就完成了判断两棵二叉树是否同构的递归实现。