動態規劃求最長公共子序列如何求最長公共子序列 _知識經驗

文章插圖
大家好,小跳來為大家解答以上的問題。如何求最長公共子序列，求最長公共子序列(動態規劃)這個很多人還不知道,現在讓我們一起來看看吧！
1、// 求LCS的長度class LCS{public: LCS(int nx, int ny, char *x, char*y); //創建二維數組c、s和一維數組a、b 。
2、并進行初始化 void LCSLength();//求最優解值（最長公共子序列長度） void CLCS();//構造最優解（最長公共子序列） ……private: voidCLCS(int i, int j); int **c, **s.m, n; char *a, *b;};int LCS::LCSLength() {for(int i=1; i<=m; i++) c[i][0]=0;for(i=1; i<=n; i++) c[0][i]=0; for (i=1; i<=m; i++)for (int j=1; j<=n; j++)if (x[i]==y[j]){c[i][j]=c[i-1][j-1]+1; s[i][j]=1; //由c[i-1][j-1]計算c[i][j]}else if (c[i-1][j]>=c[i][j-1]){c[i][j]=c[i-1][j]; s[i][j]=2; //由c[i-1][j]得到c[i][j]}else {c[i][j]=c[i][j-1]; s[i][j]=3; //由c[i][j-1]得到c[i][j]} return c[m][n];//返回最優解值} //構造最長公共子序列void LCS::CLCS(int i, int j){ if (i==0||j==0) return; if (s[i][j]==1){CLCS(i-1, j-1);cout<【動態規劃求最長公共子序列如何求最長公共子序列】本文到此分享完畢，希望對大家有所幫助。

動態規劃 求最長公共子序列 如何求最長公共子序列

動態規劃求最長公共子序列如何求最長公共子序列