Dynamic Programming — Demystified

In this post, we will unravel the core concepts of DP from scratch, and learn how to recognize problems that can be solved using this method.

Introduction

Dynamic Programming is a method for solving complex problems by breaking them down into simpler sub-problems and utilizing the fact that the optimal solution to the overall problem depends upon the optimal solution to its sub-problems.

The term “Dynamic Programming” might sound complex, especially the use of “dynamic” in the context of programming. However, it doesn’t quite mean there is something dynamic there.

In programming, the term “dynamic” is often used to denote something that changes over time or occurs at runtime, as opposed to something that is static or predetermined. But, in “Dynamic Programming,” the word “dynamic” does not have this usual meaning.

You can read more about how Richard Bellman used the term Dynamic while naming this technique here on Wikipedia.

In reality, “Dynamic Programming” does not mean “programming that is dynamic”.

Instead, it refers to a specific strategy for efficiently solving problems by breaking them down into smaller subproblems, solving each subproblem only once, and storing their solutions in case the same subproblem is needed again later.

The “programming” in dynamic programming is using the term in a way closer to “planning” or “scheduling” — so you can think of dynamic programming as “carefully planned problem-solving”.

The essence of dynamic programming is therefore not in the term itself, but in the approach it embodies:
- an efficient way to solve complex problems by breaking them down into simpler ones and reusing solutions to avoid unnecessary work.

When to use Dynamic Programming

A problem can typically be solved using DP if it has overlapping sub-problems and optimal substructure properties.

• Overlapping Sub-problems: If a problem can be broken down into sub-problems which are reused several times, then it has overlapping sub-problems.
• Optimal Substructure: If an optimal solution of a problem can be obtained by using optimal solutions of its sub-problems, then it has optimal substructure.

Memoization and Tabulation

Two main techniques in DP are memoization (top-down) and tabulation (bottom-up).

• Memoization is an optimization technique used primarily to speed up programs by storing the results of expensive function calls and reusing them when the same inputs occur again.
• Tabulation is a bottom-up approach where you solve small sub-problems first and use their solutions to solve bigger problems.

Example

Let’s illustrate dynamic programming techniques using following problem.

Problem Statement

The Fibonacci sequence is a series of numbers where a number is found by adding up the two numbers before it. The sequence starts with 0 and 1 and every number thereafter is the sum of the previous two.

Given an integer n, write a function that returns the nth number in the Fibonacci sequence.

Here’s how the Fibonacci sequence starts:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...

Solution

We will to implement this function using three different approaches:

1. Brute force (recursion)
2. Top-down dynamic programming (memoization)
3. Bottom-up dynamic programming (tabulation)

Brute Force Approach (Recursion):

We can start with a simple recursive approach to calculate Fibonacci numbers. This is the most straightforward approach, but it has serious performance issues, which we’ll discuss afterward.

Here’s the Java code for the recursive solution:

public class Fibonacci {

    // Recursive function to calculate Fibonacci
    public static int fib(int n) {
        // Base cases
        if(n <= 1) {
            return n;
        }
        // Recursive call
        else {
            return fib(n-1) + fib(n-2);
        }
    }

    public static void main(String[] args) {
        int n = 10;  
        System.out.println(fib(n));
    }
}

In the recursive solution, we have a base case for n = 0 and n = 1 since we know the Fibonacci number at these positions is the same as the input number.

For other positions, we calculate the Fibonacci number as the sum of the Fibonacci numbers at the positions n - 1 and n - 2.

Overlapping Subproblems in Brute Force Approach:

This approach results in a lot of repeated computations. If we were to draw out the recursion tree for fib(5), it would look like this:

We can see that fib(3), fib(2), fib(1)and fib(0) are being calculated multiple times. Hence this problem exhibits the key characteristic of dynamic programming called “overlapping subproblems”, as seen in the above example, fib(3), fib(2), fib(1)and fib(0) are overlapping subproblems.

Optimal Substructure in Fibonacci sequence:

In the case of the Fibonacci sequence, we see optimal substructure in the way each number in the sequence is the sum of the two preceding ones.

Let’s say we are trying to compute Fib(n). The optimal substructure property tells us that the solution to Fib(n) relies on the solutions to Fib(n-1) and Fib(n-2).

In other words, the best solution to finding the nth Fibonacci number is made up of the best solutions to finding the (n-1)th and (n-2)th Fibonacci numbers.

Here’s how it would look:

Fib(n) = Fib(n-1) + Fib(n-2)

So, if we already have the optimal solutions (i.e., the correct Fibonacci numbers) for Fib(n-1) and Fib(n-2), we can use these to construct the optimal solution for Fib(n).

That’s the intuition for optimal substructure in the Fibonacci sequence problem. We “build up” the solution to a problem from the solutions to its subproblems. And because of this property, we can use dynamic programming to solve it efficiently.

Top-Down Approach (Memoization):

To avoid repeated computations, we can use a technique called memoization. We store the result of each subproblem we solve, so if it comes up again, we can just look up the result in our ‘memo’ instead of computing it again.

Here’s the Java code for the top-down approach with memoization:

public class Fibonacci {

    // An array to store computed values
    private static int[] memo;

    // Fibonacci function with memoization
    public static int fib(int n) {
        // If the value has already been computed, return it
        if(memo[n] != -1) {
            return memo[n];
        }
        // Otherwise, compute it
        else {
            // Base cases
            if(n <= 1) {
                memo[n] = n;
            }
            // Recursive call
            else {
                memo[n] = fib(n-1) + fib(n-2);
            }
            return memo[n];
        }
    }

    public static void main(String[] args) {
        int n = 10;  
        // Initialize memo array
        memo = new int[n+1];
        for(int i = 0; i <= n; i++) {
            memo[i] = -1;
        }
        System.out.println(fib(n));
    }
}

Bottom-Up Approach (Tabulation):

The final approach is to build up to the solution from the bottom, starting with our base cases. This is called the bottom-up approach or tabulation.

Here’s the Java code for the bottom-up approach:

public class Fibonacci {

    // Fibonacci function with tabulation
    public static int fib(int n) {
        // An array to store the Fibonacci numbers
        int[] f = new int[n+1];
        // Base cases
        f[0] = 0;
        f[1] = 1;
        // Build up the Fibonacci numbers from the base cases
        for(int i = 2; i <= n; i++) {
            f[i] = f[i-1] + f[i-2];
        }
        return f[n];
    }

    public static void main(String[] args) {
        int n = 10;  
        System.out.println(fib(n));
    }
}

The intuition behind the bottom-up approach, also known as tabulation, is fundamentally about solving the problem “in order”.

In contrast to the top-down approach, where we break the problem down into subproblems and solve those first, the bottom-up approach starts by solving the smallest subproblems and gradually works up to the problem we’re interested in.

In the case of the Fibonacci sequence, the smallest subproblems are the first two Fibonacci numbers, F(0) = 0 and F(1) = 1. These are our base cases.

Now, we can observe that every subsequent Fibonacci number is the sum of the previous two. This gives us an ordering to the subproblems: to solve F(n), we first need to solve F(n-1) and F(n-2).

So, we start with n=0 and n=1, and then we gradually work our way up: we use the solutions to F(0) and F(1) to compute F(2), then use F(1) and F(2) to compute F(3), and so on, until we've computed F(n).

The advantage of this approach is that at each step, we are guaranteed to have already computed the solutions to the smaller subproblems we need. This eliminates the need for recursion and results in more efficient memory use.

Also, the bottom-up approach can be easier to reason about for certain problems, since it more closely follows the way we would naturally solve the problem by hand. It’s a process of filling in a table with solutions to subproblems in a systematic way, and this “tabulation” is why it’s also called the tabulation method.

Time and Space complexity

1. Brute Force (Recursion):

• Time Complexity: The time complexity of the recursive approach is O(2^n) in the worst case, where n is the input number. This is because at each level of recursion, the function splits into two recursive calls, leading to a binary tree of function calls. As the tree doubles in size at each level, this leads to an exponential time complexity.
• Space Complexity: The space complexity is O(n), where n is the input number. This is the space required by the call stack in a depth-first traversal of the recursion tree, which corresponds to the depth of the tree (i.e., the length of the longest path from the root to a leaf), and is equal to the input number in the worst case.

2. Top-Down Dynamic Programming (Memoization):

• Time Complexity: The time complexity of the top-down approach with memoization is O(n). We are still making a total of n recursive calls, but each call now completes in constant time, since we are simply storing precomputed values in our memoization array.
• Space Complexity: The space complexity is also O(n). We use O(n) space for the memoization array, plus O(n) space for the call stack in the recursion. So the total space complexity is O(n + n) = O(n).

3. Bottom-Up Dynamic Programming (Tabulation):

• Time Complexity: The time complexity of the bottom-up approach is O(n), where n is the input number. This is because we compute each of the n Fibonacci numbers exactly once.
• Space Complexity: The space complexity is O(n), where n is the input number. This is because we use an array of size n to store the computed Fibonacci numbers.

Bonus solution

The bottom-up solution for Fibonacci sequence can be optimized to have a constant space complexity.

If we only care about the final Fibonacci number (as opposed to the entire sequence up to that number), we can reduce the space complexity to O(1) by only keeping track of the last two Fibonacci numbers at each step.

Here’s the Java code for the bottom-up approach with constant space complexity:

public class Fibonacci {

    // Fibonacci function with constant space complexity
    public static int fib(int n) {
        // Base cases
        if(n <= 1) {
            return n;
        }

        int a = 0, b = 1;

        // Loop from 2 to n
        for(int i = 2; i <= n; i++) {
            int sum = a + b;
            a = b;
            b = sum;
        }

        // Return the n-th Fibonacci number
        return b;
    }

    public static void main(String[] args) {
        int n = 10;  
        System.out.println(fib(n));
    }
}

In this code:

• We start by initializing two integers, a and b, to 0 and 1, which are the first two numbers in the Fibonacci sequence.
• Then, we iterate from 2 to n, each time computing the next number in the sequence (a + b), and then updating a and b to be the last two numbers in the sequence.
• After the loop finishes, b contains the nth Fibonacci number, which we return.

The time complexity remains O(n), but the space complexity is now O(1), because we are using a fixed amount of space regardless of the size of n.

Please follow me if you found this content useful and also spread the word so that others can also benefit from this simple illustration of complex programming concept.