一.前言

如上

二.內容

這個問題有點抽象和復雜，我們可以看一個具體的例子。

上表如下：（我是用程序實現的）

得出公式如下：

然后用C語言實現這個具體問題。

#include<stdio.h>//求最長公共子序列的長度 //#include<string.h> int main(){int max(int a,int b);int i;//循環變量int j;//循環變量int a[7][8];char s2[7];//Bchar s1[8];//Aint n;//Aint m;//B scanf("%d",&n);//A的串長scanf("%d",&m);//B的串長scanf("%s",s1+1);//輸入A串 ，從s1[1]開始存放A串 scanf("%s",s2+1);//輸入B串 ，從s2[1]開始存放B串 for(i=0;i<=m;i++){for(j=0;j<=n;j++){if(i==0||j==0){a[i][j]=0;continue; }else if(s2[i]==s1[j]){a[i][j]=a[i-1][j-1]+1; }else {a[i][j]=max(a[i][j-1],a[i-1][j]);}}}//輸入二維數組，記錄表 for(i=0;i<=m;i++){for(j=0;j<=n;j++){printf("%d ",a[i][j]);}printf("\n");} }int max(int a,int b){//求最大值return a>b?a:b; }

經過了這個問題的探尋，可以求解原問題。
代碼如下：

#include<stdio.h>//求最長公共子序列的長度 //#include<string.h> int main(){int max(int a,int b);int i;//循環變量int j;//循環變量int a[1001][1000001];char s2[1001];//Bchar s1[1000001];//Aint m;//B int n;//Ascanf("%d",&n);//A的串長scanf("%d",&m);//B的串長scanf("%s",s1+1);//輸入A串 ，從s1[1]開始存放A串 scanf("%s",s2+1);//輸入B串 ，從s2[1]開始存放B串 s1[0]='#';s2[0]='#'; for(i=0;i<=m;i++){for(j=0;j<=n;j++){if(i==0||j==0){a[i][j]=0;continue; }else if(s2[i]==s1[j]){a[i][j]=a[i-1][j-1]+1;}else {a[i][j]=max(a[i][j-1],a[i-1][j]);}}}//顯示最長公共子序列的長度 printf("%d",a[m][n]); return 0; 輸入二維數組，記錄表 // for(i=0;i<=m;i++){ // for(j=0;j<=n;j++){ // printf("%d ",a[i][j]); // } // printf("\n"); // } }int max(int a,int b){//求最大值return a>b?a:b; }

總結

以上是生活随笔為你收集整理的动态规划问题中最长公共子序列---C语言实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。