0
我是動態規劃的新手，並使用動態編程來尋找最長的公共子序列，但是爲了更好地理解DP，我認爲這將是一個好主意在遞歸函數中的每個if-else條件中打印結果，但輸出對我沒有意義。最長公共子序列程序的逐步輸出對我來說毫無意義
例如，第一個輸出是「Now m and n both are 0」，但是爲什麼？不應該是「最後的字符B和B是否相等」？我確信編譯器正在使用一些我不知道的邏輯，但我真的想知道實際發生了什麼！
#include<iostream>
#include<cstring>
using namespace std;
int max(int a, int b)
{
return (a > b) ? a : b;
}
int lcs(char *X, char *Y, int m, int n)
{
if (m == 0 || n == 0)
{
cout << " Now m and n both are 0" << endl;
return 0;
}
if (X[m - 1] == Y[n - 1])// last character same
{
cout << " Last characters " << X[m - 1] << " & " << Y[n - 1] << "are equal " << endl;
return (1 + lcs(X, Y, m - 1, n - 1)); // add 1 + computer for rest
}
else
{
cout << " Last characters " << X[m - 1] << " & " << Y[n - 1] << "are unequal " << endl;
return max(lcs(X, Y, m, n - 1), lcs(X, Y, m - 1, n));
}
}
int main()
{
char X[] = "AGGTAB";
char Y[] = "GXTXAYB";
int m = sizeof(X)-1;
int n = sizeof(Y)-1;
cout << " LCS length is " << lcs(X, Y, m, n) << endl;
int a;
cin >> a;
}