2D Dynamic Programming
Fill a 2D table where each cell depends on adjacent cells.
LC 62 (Unique Paths), LC 64 (Min Path Sum), LC 1143 (LCS).
Unique Paths:
LCS (Longest Common Subsequence):
If
Else:
Reading direction: Always fill row-by-row, left-to-right, so sources are already computed.
dp[i][j] = dp[i-1][j] + dp[i][j-1]
— ways to reach (i,j) = ways from above + ways from left.LCS (Longest Common Subsequence):
If
A[i] == B[j]: dp[i][j] = dp[i-1][j-1] + 1Else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])Reading direction: Always fill row-by-row, left-to-right, so sources are already computed.
Filled
Current
Sources
Match (LCS)
Controls
Time: O(m·n) | Space: O(m·n)
Steps
0 stepsPress Run to trace the algorithm one step at a time.