长公共子序列长度 分数 15 作者 王东 单位 贵州师范学院 求两个字符串的最长公共子序列长度。 输入格式: 输入长度≤100的两个字符串。 输出格式: 输出两个字符串的最长公共子序列长度。

这是一个经典的动态规划问题。设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++的参考代码实现：

#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。

冒泡排序 分数 4 作者 王东 单位 贵州师范学院 冒泡排序（按升序排

冒泡排序是一种简单的排序算法，它的名字来源于元素在数组中不断“冒泡”到正确位置的过程。这个算法由王东老师（假设是正确的）在贵州师范学院教学时提及，其步骤如下：

1. **比较相邻元素**：从数组的第一个元素开始，比较相邻的两个元素，如果前一个元素大于后一个，就交换它们的位置。

2. **重复遍历**：对每一对相邻元素做同样的操作，一次遍历结束后，最大的元素就会“浮”到数组的末尾。

3. **缩小范围**：因为最后一个元素已经在正确位置了，所以在下一次遍历时，我们只对前n-1个元素进行比较和交换，其中n是数组的长度。

4. **继续直到排序完成**：重复以上步骤，每次遍历都将未排序部分的最大值放到已排序部分的末尾，直到整个数组都有序。

分数为4分可能表示这个排序方法虽然简单但效率不是很高，对于大规模数据处理来说不是最佳选择。冒泡排序的时间复杂度为O(n^2)，其中n是元素数量。