輸入: str1 = “abcde”, str2 = “ace”
輸出: 3
解釋: 最長公共子序列是 “ace”，它的長度是 3
這里用0表示空串，在代碼里用-1表示空串

一定要注意，調用函數，不要直接調用數組值
遞歸寫法：：

#include<bits/stdc++.h> using namespace std; int recdp[1000][1000]= {0}; char str1[5]= {'a','b','c','d','e'}; char str2[3]= {'a','c','e'}; int dp(int i,int j) {if(i==-1||j==-1){return 0;///兩個空串}if(recdp[i][j]){return recdp[i][j];}if(str1[i]==str2[j]){///recdp[i][j]=recdp[i-1][j-1]+1;這句寫錯了 ，一定不要亂調用recdp[i][j]=dp(i-1,j-1)+1;return recdp[i][j];}else{recdp[i][j]=max(dp(i-1,j),max(dp(i-1,j-1),dp(i,j-1)));///三個中取最大，但實時上不用，具體解是看電子書return recdp[i][j];} } int main() {//cout << "Hello world!" << endl;cout<<dp(5,2);return 0; }

---

2020.9.12復習，發現了之前代碼的問題-輸入應該是5-1，3-1

并寫了一個以0為空字符串的（邊界的）
1.當這里直接使用圖中的0為空字符串時，一定記得，str也是從0開始計算的，所以第五個字符應該是str[4]
2.不同時直接選大的（我也不知道誰大，那就比比吧）（可能，要1，可能要2，****可能都不要）
3.不需要兩個都不要，兩個都不要的話，第一次不要1，第二次不要2就行了，而且也不會，因為兩個都不要一定是最小的

#include<bits/stdc++.h> using namespace std; int recdp[1000][1000]= {0}; char str1[5]= {'a','b','c','d','e'}; char str2[3]= {'a','c','e'}; int dp(int i,int j) {///讓數組頭從開始，dp0，與dp，0都代表空串///baseif(i==0||j==0)return 0;///recif(recdp[i][j]!=0){return recdp[i][j];}///相同時直接+1/// 當這里直接使用圖中的0為空字符串時，一定記得，str也是從0開始計算的，所以第五個字符應該是str[4]//if(str1[i-1]==str2[j-1]){recdp[i][j]=dp(i-1,j-1)+1;return recdp[i][j];}else{///不同時直接選大的（我也不知道誰大，那就比比吧）（可能，要1，可能要2，****可能都不要） ///不需要兩個都不要，兩個都不要的話，第一次不要1，第二次不要2就行了，而且也不會，因為兩個都不要一定是最小的 ///*******不同時不要+1recdp[i][j]=max(dp(i-1,j),dp(i,j-1));return recdp[i][j];}return 0; } int main() {//cout << "Hello world!" << endl;cout<<dp(5,3);return 0; }

遞推寫法略有不同，str[i-1]==str[j-1] 而且一定要有空串為0

#include<bits/stdc++.h> using namespace std; int recdp[1000][1000]= {0}; char str1[5]= {'a','b','c','d','e'}; char str2[3]= {'a','c','e'}; int main() {int strlen1=5,strlen2=3;for(int i=1;i<=strlen1+1;i++){for(int j=1;j<=strlen2+1;j++){if(str1[i-1]==str2[j-1]){///注意這里recdp[i][j]=recdp[i-1][j-1]+1;}else{recdp[i][j]=max(recdp[i-1][j],recdp[i][j-1]);}}}for(int i=0;i<=strlen1;i++){for(int j=0;j<=strlen2;j++){cout<<recdp[i][j]<<" ";}cout<<endl;}return 0; }

總結

以上是生活随笔為你收集整理的最长公共子序列LCS的全部內容，希望文章能夠幫你解決所遇到的問題。

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