LeetCode 1143 Longest Common Subsequence - Walkthrough

Trace LCS on $s_1 = \text{"ABCBDAB"}$ and $s_2 = \text{"BDCAB"}$. Build the DP table. $dp[i][j]$ = LCS length of $s_1[0..i-1]$ and $s_2[0..j-1]$.

When characters match ($s_1[i-1] = s_2[j-1]$): $dp[i][j] = dp[i-1][j-1] + 1$. Otherwise: $dp[i][j] = \max(dp[i-1][j], dp[i][j-1])$. Final answer: $dp[7][5] = 4$. The LCS is "BDAB" or "BCAB". Trace back from $dp[7][5]$ to reconstruct. Backtrack from the final cell to reconstruct the actual subsequence. Follow the arrows that gave the maximum.