Recursion & DP Target: 15s
Longest Common Subsequence is a classic 2D DP. Foundation for diff algorithms.
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if a[i-1] == b[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])Type it from memory. Go.