LeetCode Dynamic Programming Pattern — From Memoization to Tabulation

What is Dynamic Programming?

Dynamic Programming (DP) is an optimization technique used when a problem has overlapping subproblems and optimal substructure. Instead of solving the same subproblem repeatedly, DP stores the result and reuses it. This typically reduces time complexity from exponential O(2^n) to polynomial O(n²) or O(n).

When to Use Dynamic Programming

Look for these patterns in problem statements:

• "Find the maximum/minimum way to..."
• "Count the number of ways to..."
• "Find the longest/shortest sequence..."
• "Can you achieve X with these items?"
• "Optimal" appears in the problem description
• The problem involves choices at each step

The Two Approaches: Top-Down vs Bottom-Up

Approach	Name	Space	When to Use
Top-Down	Memoization (Recursion + Cache)	O(n) stack + O(n) memo	Natural recursive thinking, sparse states
Bottom-Up	Tabulation (Iterative)	O(n) table (can optimize to O(1))	All subproblems needed, stack overflow risk

Top-Down Memoization Template

function solve(n) {
  const memo = new Map();
  
  function dp(i) {
    if (i <= 1) return 1; // base case
    if (memo.has(i)) return memo.get(i);
    
    const result = dp(i - 1) + dp(i - 2); // recurrence
    memo.set(i, result);
    return result;
  }
  
  return dp(n);
}

Bottom-Up Tabulation Template

function solve(n) {
  if (n <= 1) return 1;
  
  const dp = new Array(n + 1);
  dp[0] = 1; dp[1] = 1;
  
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  
  return dp[n];
}

Space Optimization

When you only need the previous 1-2 states, optimize to O(1) space:

function solve(n) {
  if (n <= 1) return 1;
  let prev2 = 1, prev1 = 1;
  
  for (let i = 2; i <= n; i++) {
    const curr = prev1 + prev2;
    prev2 = prev1;
    prev1 = curr;
  }
  
  return prev1;
}

The 6 Most Common DP Patterns

Pattern	Description	Classic Problem
1D DP (Linear)	Single sequence, decision at each step	Climbing Stairs, House Robber
2D DP (Two Sequences)	Compare two strings/arrays	LCS, Edit Distance
Knapsack (0/1)	Select items with weight constraint	Partition Equal Subset Sum
Unbounded Knapsack	Unlimited item quantities	Coin Change, Word Break
DP on Grids	Pathfinding on 2D grid	Unique Paths, Minimum Path Sum
Interval DP	Optimal choice over intervals	Matrix Chain Multiplication

Top DP LeetCode Problems by Pattern

Problem	Difficulty	Pattern
70. Climbing Stairs	Easy	1D Linear
198. House Robber	Medium	1D Linear
1143. Longest Common Subsequence	Medium	2D Two Sequences
72. Edit Distance	Medium	2D Two Sequences
322. Coin Change	Medium	Unbounded Knapsack
416. Partition Equal Subset Sum	Medium	0/1 Knapsack
62. Unique Paths	Medium	Grid DP
300. Longest Increasing Subsequence	Medium	1D + Binary Search
139. Word Break	Medium	Unbounded Knapsack
5. Longest Palindromic Substring	Medium	Expand Around Center / DP

How to Recognize a DP Problem in Interviews

1. Can the problem be broken down into smaller subproblems? → Yes = consider DP
2. Do subproblems overlap? → Yes = memoization helps
3. Does the optimal solution use optimal solutions to subproblems? → Yes = DP applies
4. Are there constraints that suggest O(n²) is acceptable? → n ≤ 1000 often implies DP

How GhOst Helps with DP Problems

• Pattern recognition: Instantly identifies whether a problem is DP, greedy, or backtracking
• State definition: Suggests what dp[i] or dp[i][j] represents
• Recurrence relation: Generates the transition formula
• Base cases: Identifies edge cases and initialization
• Space optimization: Suggests when O(1) or O(n) space is possible