用动态规划法求两个字符串 X=“acbccbaa”和 Y=“cabbcaca”的最长公共子序列。

~

设字符串x的长度为nx，字符串y的长度为ny，可新建二维数组dp[nx+1][ny+1]

dp[i][j]表示x的前i个字符x[0:i-1]与y的前j个字符y[0:j-1]之间最长公共子序列的长度

那么边界情况当i==0或j==0时，dp[i][j]=0

对于dp[i][j]，若x[i-1]==y[j-1]，在它们之前最长公共子序列dp[i-1][j-1]的基础上

再加上当前1个字符，即为新的最长公共子序列的长度，所以dp[i][j]=dp[i-1][j-1]+1；

若x[i-1]!=y[j-1]，则当前最长公共子序列的长度，继承自之前最长公共子序列的长度

即要么是dp[i-1][j]，要么是dp[i][j-1]，取两者较大值即可

令i从1遍历到nx，j从1遍历到ny，根据以上递推关系即可得出dp数组的每个元素

最终dp[nx][ny]即为nx长的字符串x与ny长的字符串y之间最长公共子序列的长度

因为遍历了二维数组的所有元素，所以算法的时间复杂度为O(nx*ny)

具体的C++代码和运行结果如下：

所给两个字符串的最长公共子序列应为"abcaa"，长度为5，与输出结果相符，望采纳~

附源码：

#include <iostream>

#include <string>

using namespace std;

int main() {

    string x = "acbccbaa", y = "cabbcaca";

    int nx = x.length(), ny = y.length();

    int dp[nx + 1][ny + 1]; // 保存最长公共子序列长度

    for (int i = 0; i <= nx; ++i)

        dp[i][0] = 0; // 边界赋值

    for (int j = 0; j <= ny; ++j)

        dp[0][j] = 0; // 边界赋值

    for (int i = 1; i <= nx; ++i) {

        for (int j = 1; j <= ny; ++j) {

            if (x[i - 1] == y[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[nx][ny] << endl; // 结果输出

    return 0;

}

---

安化县19260865734： 问一道动态规划算法题. 设A和B是长度相等,长度为n的字符串. 他们的最长公共子串长度为(n - L) - ？
龚沫思泰： 最长公共子序列(Longest-Common-Subsequence,LCS) dp[i][j]:dp[i][j]表示长度分别为i和j的序列X和序列Y构成的LCS的长度 dp[i][j] = 0,如果i=0 或 j=0 dp[i][j] = dp[i-1][j-1] + 1,如果 X[i-1] = Y[i-1] dp[i][j] = max{ dp[i-1][j], dp[i][j-1] },如果 X[i-1] != Y[i-1] LCS长度为 dp[Xlen][Ylen]

安化县19260865734： C语言:要求用递归方法编程,用迭代法求x=a的立方根 - ？
龚沫思泰： 递归方法?这些概念我没去理解.如果普通的写法:一个函数,两个参数:函数入口处, 判断满足误差?改进参数,两个参数左右互换.然后一直这样迭代下去.上述的是迭代.

安化县19260865734： 动态规划的问题:求最长公共子序列代码如下,为什么当输入两个字符串分别为“123456”以及“as”时输出 - ？
龚沫思泰： main()前面不该有int,其次for循环里如果循环变量是从0下表开始的,就该是小于strlen1和小于strlen2,没有等于

安化县19260865734： 动态规划求最短路例题？
龚沫思泰： Problem description 设A 和B 是2 个字符串.要用最少的字符操作将字符串A 转换为字符串B.这里所说的字符操作包括 (1)删除一个字符; (2)插入一个字符; (3)将一个字符改为另一个字符.将字符串A变换为字符串B 所用的最少字符操作数称为字符串A到B 的编辑距离,记为 d(A,B).试设计一个有效算法,对任给的2 个字符串A和B,计算出它们的编辑距离d(A,B). Input 输入的第一行是字符串A,文件的第二行是字符串B. Output 程序运行结束时,将编辑距离d(A,B)输出. Sample Input fxpimu xwrs Sample Output 5 请给出完整的代码

安化县19260865734： c++:编辑距离的递归实现 - ？
龚沫思泰： #include <string>#include <iostream> using namespace std; int b[51][51];//存储最小编辑距离 int op[51][51];//存储转换操作 int min(int x,int y,int z) { int temp; if(x<y) { temp=x; } else temp=y; if(z<temp) temp=z; return temp; } int opc(int x,int y,int z) ...

安化县19260865734： 怎么计算一个字符串公式的值 - ？
龚沫思泰： 把字符串拆成字符,将数字和运算符加入栈.然后每发现运算符后出现了另一个运算符比较优先级高低,弹出计算,括号不算运算符,左括号遇到右括号弹出.注意优先级.比如2*5+3/4 加一个#号--> 2*5+3/4# 进2,进*,进5,(刚要进+发现*比+优先),出2*5=10 进10,进+,进3,进/(因为/优先级高,不弹出),进4,(刚要进#,发现#优先级最高)出3/4 = 0,进0,(刚要进#,发现#优先级最高)出10+0 = 0 进#,结束

安化县19260865734： 最长公共子序列？
龚沫思泰： 这是我们的程序设计题目,下面是运行成功的代码 详细代码如下: #include <iostream.h>#include <iomanip.h>#define MAX 99//定义最大的序列长度;void main(){ int i,j,m,n,t=0; char x[MAX]={' ',' '},y[MAX]={' ',' '},a[MAX][MAX]={' '}; //初始...

安化县19260865734： 动态规划算法 急,谢了哦!!？
龚沫思泰： ab矩阵与bc矩阵相乘开销是ab^2c. 无论按什么顺序相乘,最终还是转化成两个矩阵相乘. 设N个矩阵为矩阵0到矩阵N-1. 构造2维数组(N,N),每个元素(m,n)保存矩阵m乘到n的最小消耗,那么(m,n+1)的最小消耗需要将从矩阵x(m&lt;...

安化县19260865734： 用函数调用来实现.主函数中定义两个字符串.将x=＂I ama good teacher＂Y=＂Hello good morning＂交换之. - ？
龚沫思泰： Private Sub ExchangeString(a As String, b As String) Dim t As String t = a a = b b = t End Sub Private Sub command1_click() Dim x As String, y As String x = ＂I ama good teacher＂ y = ＂Hello good morning＂ ExchangeString x, y Print ＂x=＂; x Print ＂y=＂; y End Sub

安化县19260865734： 高分求动态规划题目!!! - ？
龚沫思泰： 这是我们计算机系算法设计课的实验课程,下面是动态规划内容:实验四:动态规划实验目的:理解动态规划的基本思想,理解动态规划算法的两个基本要素最优子结构性质和子问题的重叠性质.熟练掌握典型的动态规划问题.掌握动态规划思...