Dynamic Programming

Master the art of breaking down complex problems into simpler subproblems and storing their solutions to avoid redundant calculations.

15 min read Intermediate to Advanced

What is Dynamic Programming?

Dynamic Programming (DP) is an optimization technique that solves complex problems by breaking them down into simpler subproblems. It stores the results of subproblems to avoid solving them repeatedly.

When to Use DP

A problem is a good candidate for DP if it has:

Overlapping Subproblems: Same subproblems are solved multiple times
Optimal Substructure: Optimal solution can be built from optimal solutions of subproblems

Key Concepts

State

The variables that define a subproblem uniquely (e.g., index, remaining capacity)

Transition

The relationship between states; how to compute one state from others

Base Case

The simplest cases that can be solved directly without recursion

Memoization (Top-Down)

Memoization is a top-down approach where you start with the main problem, recursively solve subproblems, and cache results for reuse.

Memoization Pattern

function solve(n, memo = {}) {
    // Check cache first
    if (n in memo) return memo[n];
    
    // Base case
    if (n <= 1) return n;
    
    // Recursive case with memoization
    memo[n] = solve(n - 1, memo) + solve(n - 2, memo);
    return memo[n];
}

Tabulation (Bottom-Up)

Tabulation is a bottom-up approach where you start with the smallest subproblems and iteratively build up to the final solution.

Tabulation Pattern

function solve(n) {
    // Initialize DP table
    const dp = new Array(n + 1).fill(0);
    
    // Base cases
    dp[0] = 0;
    dp[1] = 1;
    
    // Fill table bottom-up
    for (let i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    
    return dp[n];
}

Example: Fibonacci Sequence

Approach	Time	Space
Naive Recursion	O(2ⁿ)	O(n)
Memoization	O(n)	O(n)
Tabulation	O(n)	O(n)
Space Optimized	O(n)	O(1)