Leetcode 509: Fibonacci Number

Problem description

Dynamic programming (DP)

As a method's name, dynamic programming is not descriptive of what it is designed to do (for historical reasons not detailed here). The method breaks a problem down into simpler subproblems recursively or iteratively, solving each subproblem just once, storing solutions in case they need to be solved again (via memoization in the top-down, recursive approach and tabulation in the bottom-up, iterative approach).

DP fundamentally falls within the “divide and conquer” algorithm umbrella — problems suitable for this technique can be divided into smaller sub-problems that could be solved first. Finally, the results of the subproblems are combined to obtain a global, optimal solution.

Hallmarks of DP applicability: Overlapping subproblems

Different from other divide-and-conquer algorithms such as binary search, problems suitable for DP have overlapping subproblems. Concretely, this further translates to a repeated reuse of solutions to earlier subproblems. For example, Fibonacci number reuses solutions F(n — 2) and F(n — 1) in F(n) = F(n — 2) + F(n — 1); Pascal’s triangle always reuses results from the previous row. To avoid recomputation, DP comes to rescue by storing previous results, so that we only need to have a way to extract them when they are reused.

Every recursive solution also has an iterative counterpart — DP is no exception:

• Top-down recursive DP with memoization
• Bottom-up iterative DP with tabulation

What is top-down and what is bottom-up, exactly?

Let’s use the Fibonacci number problem at hand as a concrete example:

Top-down

• Top: This refers to the original or final problem that we want to solve
• Bottom: As we break the main problem into smaller subproblems (recursively in top-down DP), we are moving “down” towards the base cases
• Method: Typically involves recursion (and this immediately introduces space overhead from recursive call stack). We start from the main problem at the top (what we eventually want) and break it down into smaller subproblems. We typically use memoization to store and reuse solutions to subproblem solutions that are already solved along the way to avoid recomputation
• Examples related to the current problem: When finding the nth Fibonacci number with top-down DP, we start with fib(n), and this function would in turn call fib(n-1) and fib(n-2) until we reach the base case. This is a top-down approach since we start with the main problem and break it down (i.e., we start from the top and go down to reach the base). Memoization, a caching technique to avoid recalculation, is implemented via hash table.

Bottom-up

• Bottom: Referes to the smallest subproblems or the base cases
• Up: As we build solutions to larger problems using solutions of these smaller subproblems, we are moving up towards the solution of the main problem
• Method: Typically involves iteration, and note that iterative solution uses a sliding window approach that inherently avoids recomputation. If results at each step need to be stored to build the final output, we use tabulation where we store the solutions in a table (typically as a 1-D or 2-D array) and we fill it up in a systematic way (Pascal’s triangle is a great visual example of this systematic fill-up)
• Examples related to the current problem: We start by initializing the values of fib(0) and fib(1) and iteratively compute fib(2), fib(3), and so on, until fib(n). This bottom-up approach builds the solution from the ground up

Python solutions

Top-down recursive DP with memoization

class TopDownSolution:
    def fib(self, n: int) -> int:
        """Recursion with memoization"""
        # Initialize the memo cache with base case solutions
        memo = {0: 0, 1: 1}

        if n not in memo:
            # Recursive calls with memoization
            memo[n] = self.fib(n - 2) + self.fib(n - 1)

        return memo[n]

Complexity of the top-down solution

• Space complexity: O(n), since each Fibonacci number from 2 to n is computed once and result is stored and fetched with O(1) time
• Time complexity (+ overhead of recursive call):
  - O(n) for the recursive call stack
  - O(n) for the memoization hash table
  Collectively, we need O(n) + O(n) = O(n) space

Note, partly due to the overhead of the recursive call, although the time complexity is O(n) explicitly, the runtime is noticeably slower than iterative solution.

Bottom-up iterative DP

class BottomUpSolution:
    def fib(self, n: int) -> int:
        if n <= 1:
            return n

        # Initialize the value of fib(0) and fib(1)
        fib_n_minus_2, fib_n_minus_1 = 0, 1

        # Iteratively compute fib(2), fib(3), and so on
        #   Mind the edge! Stop at (n+1) to ensure that fib_n is computed
        for _ in range(2, n + 1):
            fib_n = fib_n_minus_2 + fib_n_minus_1

            # slide window by one step
            fib_n_minus_2 = fib_n_minus_1
            fib_n_minus_1 = fib_n

        # At the end of the loop, fib_n_minus_1 holds the value of fib(n)
        #   and fib_n_minus_2 holds the value of fib(n-1)
        # Hence return fib_n_minus_1
        return fib_n_minus_1

Complexity of the bottom-up solution

• Space complexity: O(1), since no additional data structure is required
• Time complexity: O(n), since we iterate from 2 to n, and we only compute each Fibonacci number once

Unit test examples (with pytest)

import pytest


@pytest.mark.parametrize(
    "n, expected", [(0, 0), (1, 1), (2, 1), (3, 2), (4, 3), (5, 5), (6, 8)]
)
class TestFibonacci:
    def test_top_down_solution(self, n, expected):
        solution = TopDownSolution()
        assert solution.fib(n) == expected

    def test_bottom_up_solution(self, n, expected):
        solution = BottomUpSolution()
        assert solution.fib(n) == expected