Dynamic Programming

Dynamic programming (DP) is one of the most powerful algorithmic techniques in computer science. It’s a favorite topic in technical interviews at top companies because it transforms seemingly intractable problems into elegant and efficient solutions.

What is Dynamic Programming?

Dynamic programming is an optimization technique that solves complex problems by breaking them down into simpler subproblems. The key insight is that many problems have overlapping subproblems that we solve repeatedly. DP stores the results of these subproblems to avoid redundant calculations.

Think of it as smart recursion with memory. We remember what we’ve already computed, so we don’t waste time recalculating the same things over and over.

Understanding Dynamic Programming using a real-life example

Imagine you’re climbing a staircase with 10 steps, and you can take either 1 or 2 steps at a time. How many different ways can you reach the top?

You could solve this from scratch by listing every possible combination, but that quickly becomes overwhelming. Instead, you realize: to reach step 10, you must have come from either step 9 or step 8. So the number of ways to reach step 10 would be equal to the number of ways to reach step 9 plus the number of ways to reach step 8.

So, we start from the bottom:

• Step 1: 1 way
• Step 2: 2 ways (1+1 or 2)
• Step 3: 3 ways (all ways to step 1 + all ways to step 2)
• Step 4: 5 ways (all ways to step 2 + all ways to step 3)

Each step builds on previously solved steps. You never recalculate; you just reuse answers you’ve already found.

This is exactly how dynamic programming works: break a problem into smaller subproblems, solve each subproblem once, store the results, and build the final answer by reusing those stored solutions.

Why Dynamic Programming is effective

The effectiveness of dynamic programming stems from a fundamental principle: the reuse of computations. In many algorithms, the same calculations are performed repeatedly, wasting valuable processing time. Dynamic programming eliminates this waste by solving each unique subproblem exactly once and storing the result for future reference.

Consider the performance difference this creates. A naive recursive solution to finding the 40th Fibonacci number might perform over a billion function calls. Using dynamic programming, the same problem requires only 40 calculations. For larger inputs, this optimization becomes even more critical, often reducing hours of computation to mere seconds.

Top-down vs. bottom-up approach

Dynamic programming solutions typically take one of two forms:

1. Top-down with memoization
2. Bottom-up with tabulation

Both approaches solve the same problems and achieve similar time complexity, but they differ in implementation style and have different practical trade-offs.

Top-down approach

The top-down approach uses memoization to avoid redundant calculations. It starts with the original problem and recursively breaks it down into smaller subproblems. Each time a subproblem is solved, its result is stored in a cache or lookup table. Before solving any subproblem, the algorithm checks whether the result is already available. If it is, the cached result is returned immediately. If not, the algorithm computes the result, stores it, and then returns it.

Let’s take a look at the following Fibonacci call tree that illustrates the top-down approach:

Starting from fib(4), the algorithm recursively breaks down the problem: fib(4) calls fib(3) and fib(2), which in turn expands into smaller subproblems, continuing until we reach the base cases of fib(1) and fib(0). However, notice that fib(2) and fib(1) appear twice in the tree. Instead of recomputing these values each time they’re needed, we store them in a lookup table (cache) after the first calculation. When we encounter fib(2) or fib(1) again in a different branch, we simply retrieve the precomputed result from the table rather than going through the entire recursive process again.

Here’s a sample Python implementation of the top-down approach:

def fib(n, memo=None):
    # Initialize the memoization dictionary
    if memo is None:
        memo = {}
    
    # Base cases
    if n == 0:
        return 0
    if n == 1:
        return 1
    
    # Check if result is already in the lookup table
    if n in memo:
        return memo[n]
    
    # Compute the result recursively
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
    
    # Return the cached result
    return memo[n]

This is why top-down DP is often described as “recursion with memory.” The recursive structure remains, but duplicate subtrees are replaced by instant lookups. Instead of an exponential explosion of redundant calculations, we perform each unique computation only once. The call tree may look complex, but memoization ensures we’re doing far less work than it appears.

Bottom-up approach

The bottom-up approach works in the opposite direction. Instead of starting at the top and working down, you begin with the smallest subproblems whose solutions are trivial or given as base cases.

For example, fib(0) and fib(1) in the case of a Fibonacci sequence.

You then systematically build up to larger subproblems, such as fib(2), fib(3), and fib(4), ensuring that when you need to solve any subproblem, all smaller subproblems it depends on have already been solved.

Here’s a visual walkthrough of computing fib(4) using the bottom-up approach:

1 / 6

This approach eliminates recursion overhead entirely and often uses memory more efficiently. The iterative nature makes it easier to optimize space complexity since you can identify exactly which previous values you need to keep. The main challenge with this approach is determining the correct order to solve subproblems, which requires understanding the dependency structure of your problem. Once you establish this order, implementation is typically straightforward and efficient.

Let’s have a look at the sample Python implementation of the bottom-up approach:

def fib(n):
    # Handle base cases
    if n == 0:
        return 0
    if n == 1:
        return 1
    
    # Create a table to store results
    dp = [0] * (n + 1)
    
    # Initialize base cases in the table
    dp[0] = 0
    dp[1] = 1
    
    # Build up from smallest subproblems to larger ones
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    
    # Return the final result
    return dp[n]

Examples of DP

The following examples illustrate some problems that can be solved using Dynamic Programming:

• Minimum path sum: Given an m × n grid of non-negative integers, find the minimum-sum path from the top-left to bottom-right cell. You can only move right or down.

• Pascal’s triangle: Given an integer numRows, generate the first numRows of Pascal’s Triangle. In a Pascal’s Triangle, each number is the sum of the two numbers directly above it. The triangle always starts with a single 1 at the top, and every row begins and ends with the number 1.

1 / 5

When to use Dynamic Programming

Identifying a DP problem is a skill in itself. While most problems that require DP follow recognizable patterns, they all share two fundamental mathematical properties. If a problem meets these two criteria, DP is likely the right approach.

1. The two core properties
   1. Overlapping subproblems: The problem can be broken down into smaller versions of itself, and those smaller versions are calculated multiple times. For example, in a Fibonacci tree, fib(3) is calculated in multiple branches. DP remembers fib(3) so we only compute it once.
   2. Optimal substructure: The best solution to the big problem is built directly from the best solutions of its smaller parts. If you want the shortest path from City A to City C, and that path goes through City B, then the A-to-B portion must also be the shortest possible path between those two cities.
2. The DP litmus test: Beyond the formal definitions, look for these “red flags” in a problem description that almost always point to Dynamic Programming:
   1. The “maximum/minimum” request: If a problem asks for the longest path, the minimum cost, or the maximum profit, it’s often a DP problem.
   2. Counting choices: If you are asked to find the total number of ways to do something (e.g., “How many ways can you climb these stairs?”), you are likely looking for a DP solution.
   3. The “choice” factor: Does each step involve a binary choice (e.g., “Should I take this item or leave it?”) where the decision affects your future options? This is a hallmark of the 0/1 Knapsack pattern.

Interview tips and tricks

When approaching dynamic programming problems in technical interviews, keep these practical strategies in mind to maximize your success and demonstrate clear problem-solving skills.

1. Start with brute-force: don’t jump straight to DP. Write the recursive solution first, identify the overlapping subproblems, then add memoization.
2. Draw it out: For grid problems, draw the grid and fill in values by hand for small examples. This helps you see the pattern.
3. State your approach: In interviews, verbalize your thought process:
   1. “I notice this has overlapping subproblems…”
   2. “Let me define dp[i] as…”
   3. “The recurrence relation would be…”
4. Consider space optimization: After getting a working solution, ask: “Can I reduce the space complexity?” Often, you can reduce from O(n²) to O(n) or O(n) to O(1).
5. Test with examples: Walk through your solution with the example cases. DP bugs are often in:
   1. Base cases
   2. Loop boundaries
   3. Index calculations
6. Know the Classics: The problems in this guide appear frequently in interviews. Master these, and you’ll recognize variations.