I am trying to implement the Longest Common Subsequence (LCS)

problem using dynamic programming in C++.

I understand the basic concept, but I am confused about

how to build the DP table and trace back the actual subsequence.

Here is my current code:

#include 
#include 
using namespace std;

int lcs(string s1, string s2) {
    int m = s1.length();
    int n = s2.length();
    int dp[m+1][n+1];
    
    for(int i = 0; i <= m; i++) {
        for(int j = 0; j <= n; j++) {
            if(i == 0 || j == 0)
                dp[i][j] = 0;
            else if(s1[i-1] == s2[j-1])
                dp[i][j] = dp[i-1][j-1] + 1;
            else
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
        }
    }
    return dp[m][n];
}

int main() {
    string s1 = "ABCBDAB";
    string s2 = "BDCAB";
    cout << "LCS Length: " << lcs(s1, s2) << endl;
    return 0;
}