Page 33Dynamic Programming

33 — LCS

DP grid visual and reconstruction of longest common subsequence.

LCS DP grid

X Y

if X[i-1] == Y[j-1]: dp[i][j] = 1 + dp[i-1][j-1] else: dp[i][j] = max(dp[i-1][j], dp[i][j-1])

Time: O(mn), Space: O(mn). Reconstruction follows arrows backward from bottom-right.