Introduction

Dynamic Programming is an algorithmic technique that optimizes exhaustive search by storing and reusing subproblem results. In essence, it breaks a complex problem into overlapping subproblems and solves each subproblem only once, saving the answers for future use. This approach greatly improves efficiency – in fact, applying DP can often reduce an exponential-time brute-force solution down to polynomial time.

DP is commonly applied in coding interviews for problems that involve combinatorial search or optimization, especially when a naive recursion would repeat the same computations. It tends to appear in medium to hard interview questions at top companies whenever the problem hints at reusable sub-results or a need to consider many possible combinations.

When to Think DP

Look for certain cues in problem descriptions that suggest DP may be applicable:

• Overlapping Subproblems: The problem can be broken into smaller sub-tasks that repeat. (E.g. naive recursion revisits the same states or inputs multiple times.)
• Optimal Substructure: An optimal solution can be formed by combining optimal solutions of subproblems. (For example, the shortest path in a graph can be built from shortest subpaths.)
• Combinatorial Choices: The problem asks for a max/min value or count of ways to do something (e.g. “find the longest...”, “count the number of ways...”).
• Decision Sequence: You need to make a sequence of choices (include/exclude an item, take an action or not, etc.) and find the best outcome.
• Constraint-Based Paths: Problems like grid paths, sequence alignments, or partitioning (e.g. coin change, text segmentation) where you build a solution step by step.

In an interview, if a brute-force solution would clearly explode combinatorially and you notice repeated patterns, it’s a strong sign that DP (with memoization or tabulation) is the intended optimization. Recognizing these patterns is key.

Core Idea / Mental Model

At its core, Dynamic Programming is about solving subproblems once and reusing their solutions. Rather than recalculating the same thing multiple times, we store results in a table or cache (memoization) and look them up when needed. This is like having a cheat-sheet of solved smaller cases that you refer to as you build up the solution to the big problem.

A good mental model for DP is “solving a puzzle by first solving its pieces.” Imagine a large jigsaw puzzle: you might first solve small sections (subproblems) and then combine these sections. Dynamic programming works the same way: solve and remember solutions to smaller parts, then use those to assemble solutions to larger parts. Another intuition: DP is essentially “recursion with a memory.”

In summary, dynamic programming leverages two key properties: overlapping subproblems and optimal substructure. If you can identify these, you can apply DP by defining appropriate subproblem states, finding relationships (recurrence) between states, and caching intermediate results.

Base Template (Python - Bottom-Up DP)

Most DP solutions follow a similar template: define a state representation, set up base cases, then use a recurrence relation to fill a table or compute recursively with memoization. Below is a Python example of a bottom-up DP template for counting ways to climb n stairs (1 or 2 steps at a time).

def count_ways_to_climb(n):
    # 1. Define DP table (list) of size n+1
    dp = [0] * (n + 1)
    
    # 2. Base cases
    dp[0] = 1  # 1 way to climb 0 stairs (do nothing)
    if n >= 1:
        dp[1] = 1  # 1 way to climb 1 stair (1 step)
    
    # 3. State transition: fill dp[i] using subproblem solutions
    for i in range(2, n + 1):
        # Ways to reach step i = ways to reach i-1 + ways to reach i-2
        dp[i] = dp[i - 1] + dp[i - 2]
        
    # 4. The final answer for n stairs is in dp[n]
    return dp[n]

Template Explained: dp[i] stores the number of ways to reach step i. Base cases dp[0] and dp[1] are initialized. The loop then fills the table using the recurrence dp[i] = dp[i-1] + dp[i-2]. This bottom-up pattern is common in DP.

Interactive Animation (Climbing Stairs DP)

The animation below illustrates the bottom-up DP computation for the climbing stairs problem (e.g., n = 4). Watch how the dp table is filled, with each cell dp[i] relying on previously computed values dp[i-1] and dp[i-2].

1. Initialization: dp table for n stairs. dp[0]=1, dp[1]=1.
2. Compute dp[2] = dp[1] + dp[0].
3. Compute dp[3] = dp[2] + dp[1].
4. ...and so on, until dp[n] is filled.

Major Types of Dynamic Programming

Dynamic Programming isn’t a single technique, but a family of approaches. Here’s a breakdown of major DP variations:

Top-Down (Memoization)

Formulate solution recursively, use a cache (memo) to save results. Starts from original problem, breaks it down. Checks memo before solving subproblem. Essentially "recursion with caching." Good for naturally recursive problems or when not all subproblems are needed. Watch for recursion depth.

Bottom-Up (Tabulation)

Iteratively build solutions from simplest subproblems (base cases) up to the original problem. Fills a DP table in a specific order. No recursion overhead. Good when subproblem range is known and iteration order is clear. Easier for space optimization.

1D DP Optimization

Reduces space by using a 1D array (or few variables) if recurrence only needs recent states (e.g., dp[i] depends only on dp[i-1], dp[i-2]). Example: Fibonacci, Knapsack (space-optimized). Useful when memory is limited.

State Compression

Encodes a state with multiple attributes into a single representation (often a bitmask) to make DP feasible. Bitmask DP uses an N-bit integer for N elements/choices. Useful for combinatorial problems on small N (e.g., TSP, subset problems, N ~ 20). Complexity often O(2^N * poly(N)).

Decision DP (Knapsack/Rod Cutting)

At each step, face a choice among options; DP explores all to find an optimum or count. State includes progress (e.g., items considered, remaining capacity/length). Transition is often max/min over choices. Used when greedy fails and all possibilities must be considered efficiently.

Interval DP

For problems on an interval [l,r] where solution involves splitting it. State dp[l][r]. Recurrence combines solutions of sub-intervals. Examples: Matrix Chain Multiplication, Optimal Binary Search Tree. Often O(n^3) time. Use when subproblems are naturally "segments."

Bitmask DP

A specific application of state compression using bitmasks to represent subsets or states. Often used for problems like Traveling Salesman Problem (TSP), Hamiltonian paths, or assignment problems where N is small (≤ 20-22). Allows DP over all 2^N subsets.

Tree DP

DP applied to tree structures. State dp[node][...] considers the subtree rooted at node. Uses DFS: compute results for children, then combine for parent. For problems like largest independent set in a tree, tree coloring, counting paths. Subproblems are "rooted subtrees."

Mastery involves recognizing these patterns and applying the appropriate DP variant.

Time & Space Complexity

The complexity of a DP solution is generally O(Number of States × Transition Cost).

Top-Down (Memoization)

Time: Number of unique states computed. For 1D DP (Fibonacci/stairs), O(n). For 2D DP, O(nm).
Space: O(Number of States) for memo table + O(Recursion Depth) for stack. Fibonacci: O(n) space.

Bottom-Up (Tabulation)

Time: Similar to top-down, O(Number of States × Work per State).
Space: O(Number of States) for DP table. No recursion stack. Can often be optimized (e.g., to O(1) or O(n) from O(n*m)).

DP turns potential exponential complexity into polynomial time by avoiding repeated work.

Common Pitfalls

Dynamic programming can be tricky. Watch out for these common mistakes:

Thorough testing on small examples and edge cases helps catch these mistakes.