Tabulation

1. 1.Fibonacci Number
   1D Table: dp[i] = dp[i-1] + dp[i-2] with dp[0]=0, dp[1]=1easy
2. 2.Climbing Stairs
   1D Table: dp[i] = dp[i-1] + dp[i-2] initialized at base step 0 and 1easy
3. 3.Min Cost Climbing Stairs
   1D Table: dp[i] = cost[i] + min(dp[i-1], dp[i-2])easy
4. 4.House Robber
   1D Table: dp[i] = max(dp[i-1], nums[i] + dp[i-2])medium
5. 5.Coin Change
   1D Unbounded min table: dp[a] = min(dp[a], 1 + dp[a-coin]) initialized to INFmedium
6. 6.Coin Change II
   1D Combination count table: dp[a] += dp[a-coin] with outer coin loopmedium
7. 7.Partition Equal Subset Sum
   1D 0/1 Knapsack boolean table: right-to-left loop target = sum/2medium
8. 8.0/1 Knapsack
   1D Capacity table: right-to-left loop ensures single item usagemedium
9. 9.Unbounded Knapsack
   1D Capacity table: left-to-right loop allows multiple item usagemedium
10. 10.Unique Paths
    2D Grid Table: dp[r][c] = dp[r-1][c] + dp[r][c-1]medium
11. 11.Minimum Path Sum
    2D Grid Table: dp[r][c] = grid[r][c] + min(dp[r-1][c], dp[r][c-1])medium
12. 12.Longest Common Subsequence
    2D Matrix: match -> 1 + dp[i-1][j-1], else max(top, left)medium
13. 13.Edit Distance
    2D Matrix: match -> dp[i-1][j-1], else 1 + min(insert, delete, replace)medium
14. 14.Longest Increasing Subsequence
    1D Table: dp[i] = 1 + max(dp[j]) for all j < i with nums[j] < nums[i]medium
15. 15.Decode Ways
    1D Table: dp[i] += dp[i-1] (if 1-digit valid) + dp[i-2] (if 2-digit valid)medium
16. 16.Word Break
    1D Table: dp[i] = true if dp[j] && wordDict.contains(s[j:i])medium
17. 17.Longest Palindromic Subsequence
    2D Substring Table: fill by substring length 1 to Nmedium
18. 18.Target Sum
    1D Subset Sum table: convert target to subset sum P = (sum + target)/2medium
19. 19.Triangle Minimum Path Sum
    Bottom-up accumulation: dp[r][c] += min(dp[r+1][c], dp[r+1][c+1])medium
20. 20.Maximal Square
    2D Matrix: dp[r][c] = 1 + min(top, left, diagonal) for 1smedium

1. 21.Perfect Squares
   1D Unbounded min table: dp[i] = min(dp[i], 1 + dp[i - s*s])medium
2. 22.Combination Sum IV
   1D Permutation table: outer target loop, inner coin loopmedium
3. 23.Distinct Subsequences
   2D Matrix count table: match -> dp[i-1][j-1] + dp[i-1][j]hard
4. 24.Interleaving String
   2D Matrix boolean table: dp[i][j] checks s1[i-1] and s2[j-1]medium
5. 25.Minimum Falling Path Sum
   Grid DP row-by-row: dp[r][c] = cell + min(left, center, right)medium
6. 26.Dungeon Game
   Reverse Grid Table: fill bottom-right to top-left for min healthhard
7. 27.Stock Buy/Sell DP
   State Machine Table: holding vs free states filled day 0..Nmedium
8. 28.Palindrome DP
   2D Table filled by substring length from 1 to Nmedium
9. 29.Interval DP
   Matrix Chain / Burst Balloons: length-based diagonal fillhard
10. 30.DP Space Optimization
    Rolling array technique: reduce O(N*M) table to 2 rows or 1 rowmedium

1. Can I start from known base answers?Tabulation
2. Can I compute states in dependency order?Bottom-Up DP
3. Want to avoid function call stack overhead?Tabulation
4. Dependencies move left-to-right?Loop 0 to N
5. 0/1 Knapsack space optimization?Loop capacity Right-to-Left

package main

import "fmt"

// 2D Matrix Tabulation for Longest Common Subsequence
func lcsTabulation(text1, text2 string) int {
    m, n := len(text1), len(text2)
    // Create DP table initialized to 0 (base cases for empty strings)
    dp := make([][]int, m+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
    }

    // Fill in dependency order (top-left to bottom-right)
    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if text1[i-1] == text2[j-1] {
                // Invariant: match comes from ↖ diagonal
                dp[i][j] = 1 + dp[i-1][j-1]
            } else {
                // Invariant: mismatch comes from max of ↑ top or ← left
                if dp[i-1][j] > dp[i][j-1] {
                    dp[i][j] = dp[i-1][j]
                } else {
                    dp[i][j] = dp[i][j-1]
                }
            }
        }
    }
    return dp[m][n]
}

// 1D Rolling Array Space Optimization O(N) space
func lcsSpaceOptimized(text1, text2 string) int {
    m, n := len(text1), len(text2)
    prev := make([]int, n+1)
    curr := make([]int, n+1)

    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if text1[i-1] == text2[j-1] {
                curr[j] = 1 + prev[j-1]
            } else {
                if prev[j] > curr[j-1] {
                    curr[j] = prev[j]
                } else {
                    curr[j] = curr[j-1]
                }
            }
        }
        copy(prev, curr)
    }
    return prev[n]
}

func main() {
    fmt.Println("LCS 2D Table:", lcsTabulation("abcde", "ace"))        // 3
    fmt.Println("LCS 1D Optimized:", lcsSpaceOptimized("abcde", "ace")) // 3
}

Core Tabulation Structure & Order

Base Cases → Choose Order → Fill Loops → Target Cell
0/1 Knapsack 1D Table → Loop capacity Right-to-Left
Unbounded Knapsack 1D Table → Loop capacity Left-to-Right
2D Matrix Matching → dp[i][j] uses ↖ diagonal, ↑ top, ← left
Space Optimization → Rolling arrays reduce dimensions after table verification

Tabulation Variants & Loop Dynamics

Common Interview Mistakes

• • Filling the table before explicitly defining what dp[cell] represents.
• • Wrong base case initializations (e.g. initializing min problems with 0 instead of INF, or combinations with 0 instead of dp[0]=1).
• • Incorrect iteration order where a cell is computed before its dependencies are ready.
• • Running 0/1 Knapsack 1D capacity loop left-to-right (accidentally allowing unlimited item reuse).
• • Failing to realize that changing outer/inner loop nesting converts combinations into permutations.
• • Overwriting DP values prematurely during space optimization before previous row values are fully read.
• • Allocating a massive 2D matrix without checking constraint sizes (causing Memory Limit Exceeded).
• • Forcing bottom-up tabulation on tree problems when postorder DFS memoization is cleaner.
• • Off-by-one errors on string DP tables (forgetting +1 size for empty prefix base cases).
• • Returning dp[N] when the target is at dp[N-1] or vice-versa.

Interview Rules

Start from Base Cases → Fill Bottom-Up Table
Rule 1                → Define dp[state] cell meaning explicitly
Rule 2                → Initialize base case boundary cells
Rule 3                → Determine dependency direction before looping
Rule 4                → 0/1 Knapsack 1D = Right-to-Left loop
Rule 5                → Unbounded Knapsack 1D = Left-to-Right loop
Rule 6                → Space optimization: reduce table after table works
Time Complexity       → Total States × Transitions per State
Space Complexity      → Table Size (O(N*M), O(N), or O(1))

💡 Golden Rule: Start from states whose answers you already know, then fill every new state only after all states it depends on are ready.

Tabulation = Bottom-Up DP (Base Cases → Target)
5-Step Pattern: Table → Base → Order → Fill → Target
0/1 Knapsack 1D = Right-to-Left loop
Unbounded Knapsack 1D = Left-to-Right loop
Loop order changes combinations vs permutations
Sequential memory locality makes tabulation fast
Calculate state count before allocating large tables