LeetCode 1143 Longest Common Subsequence - Reconstruction

The DP (dynamic programming) gives you the length. To find the actual LCS (Longest Common Subsequence), backtrack from $dp[m][n]$:

$1.$ If A[i-1] = B[j-1], this character is in the LCS. Add it, move to $(i-1, j-1)$.

$2.$ If $dp[i-1][j] > dp[i][j-1]$, move to $(i-1, j)$.

$3.$ Otherwise, move to $(i, j-1)$.

$4.$ Stop when you hit row 0 or column 0. Reverse the collected characters to get the LCS. Multiple valid LCS may exist if there are ties.