Stage 1 · Code
Dynamic Programming
Tabulation
Bottom-up DP with table filling.
6 min readMastering Data Structures & Algorithms for Software Engineering InterviewsCode
Tabulation Concept
Tabulation = bottom-up DP. Build table iteratively from base cases up to target. Fill table in order where dependencies are already computed. No recursion, no call stack.
Fibonacci Tabulation
Gobottom-up-fibonacci.go
10 linesLn 1, Col 1Go
Base cases dp[0], dp[1]. Fill forward: each dp[i] depends on previous two. O(n) time, O(n) space.
Space Optimization
If recurrence only depends on last k values, keep only those k variables. Fibonacci needs last 2 → O(1) space.
Goo(1)-space-fibonacci.go
9 linesLn 1, Col 1Go
Only track last two values. Shift variables each iteration. Most efficient for single query.
Determining Fill Order
Dependency graph determines fill order. For 1D: left→right (if dp[i] needs dp[i-1]) or right→left. For 2D: row by row, col by col, or diagonal. Key: when computing dp[i], all dependencies must be filled.
| Recurrence | Fill Order |
|---|---|
| dp[i] = dp[i-1] + dp[i-2] | i = 2..n (left to right) |
| dp[i] = dp[i+1] + dp[i+2] | i = n-2..0 (right to left) |
| dp[i][j] = dp[i-1][j] + dp[i][j-1] | Row 0..m, Col 0..n (top-left to bottom-right) |
| dp[i][j] = dp[i+1][j] + dp[i][j+1] | Row m-1..0, Col n-1..0 (bottom-right to top-left) |
| dp[i][j] = dp[i-1][j-1] + ... | Diagonals (i+j constant) |
Mark this lesson complete to store local progress and unlock a cleaner resume path the next time you visit.