Dynamic Programming Introduction

Notes of Dynamic Programming

Dynamic Programming: An Introduction with Fibonacci

What Is Dynamic Programming?

Dynamic Programming (DP) is an optimization technique used to avoid redundant calculations, by remembering the results of subproblems we've already solved.

There are two main ways to apply Dynamic Programming:

1. Memoization (Top-Down): We store the results of subproblems in a map or an array, so we never have to recompute them. This is especially useful when subproblems overlap (the same subproblem shows up more than once).
2. Tabulation (Bottom-Up): Instead of starting from the big problem and breaking it down, we start from the base cases, and build our way up iteratively to the final answer. This approach avoids using recursion, which also saves on the memory used by the recursion call stack.

There's also a further improvement we can apply on top of these:

3. Space Optimization: By looking closely at what a subproblem actually depends on (for example, in Fibonacci, we only ever need the previous two results), we can often reduce the space used from O(N) down to O(1).

Example: The Fibonacci Sequence

The Fibonacci sequence is defined as:

F(N) = F(N-1) + F(N-2)

Let's look at how this can be solved in four different ways, each one an improvement over the last.

1. Plain Recursive Solution

This is the most direct way to write the Fibonacci formula in code — but it's also the least efficient, since it ends up solving the same subproblems over and over again.

function fibonacci(n) {
    if (n <= 1) {
        return n;
    }

    return fibonacci(n - 1) + fibonacci(n - 2);
}

• Time Complexity: O(2ⁿ)
• Space Complexity: O(n)

2. Memoization (Top-Down)

Here, we store the result of each Fibonacci number the first time we calculate it, in an object called memo. If we ever need that same value again, we just look it up instead of recalculating it.

function fibonacci(n, memo = {}) {
    if (n <= 1) {
        return n;
    }

    if (memo[n] !== undefined) {
        return memo[n];
    }

    memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);

    return memo[n];
}

• Time Complexity: O(n)
• Space Complexity: O(n)

3. Tabulation (Bottom-Up)

Instead of starting from n and breaking it down with recursion, we start from the base cases (F(0) and F(1)), and build our way up to F(n) using a simple loop and an array to store each result along the way.

function fibonacci(n) {
    if (n <= 1) {
        return n;
    }

    let dp = new Array(n + 1);

    dp[0] = 0;
    dp[1] = 1;

    for (let i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[n];
}

• Time Complexity: O(N)
• Space Complexity: O(N)

4. Space-Optimized Version

Looking closely at the tabulation approach, we notice something useful: to calculate dp[i], we only ever need the two previous values — dp[i-1] and dp[i-2]. We don't actually need to keep the entire array of past results around.

So instead of an array, we just keep track of the two most recent values using two variables, updating them as we go.

function fibonacci(n) {
    if (n <= 1) {
        return n;
    }

    let prev2 = 0; // fib(0)
    let prev1 = 1; // fib(1)

    for (let i = 2; i <= n; i++) {
        let current = prev1 + prev2;

        prev2 = prev1;
        prev1 = current;
    }

    return prev1;
}

• Time Complexity: O(n)
• Space Complexity: O(1)

Summary

As you can see, each step brings a clear improvement — from the very slow plain recursive version, all the way down to a version that uses only a constant amount of extra memory.