Definition

Dynamic Programming is a very powerful programming paradigm that can be employed to find optimal solutions to problems that possess the following properties: overlapping subproblems and optimal substructure.

  • Overlapping subproblems
    • A problem can be decomposed into smaller subproblems than can be reused multiple time to construct the overall solution
    • The solutions to subproblems are often memoized to avoid re-work and improve time complexity
    • Solutions to subproblems are reused more than once by subsequent solutions
  • Optimal substructure
    • The optimal solution to a problem can be constructed from the optimal solution of overlapping subproblems. (The shortest path between three cities can be found by finding the shortest path to the second city, and then building from there to find the shortest path to the third city)

Calculating the nth Fibonacci number is a classic dynamic programming problem: F(n) = F(n-1) + F(n-2). Since the solution to F(n) reuses F(n-1) and F(n-2), we say that the problem has optimal substructure. We say the problem has overlapping subproblems because each solution is reused more than once. For example, F(4) is used to solve F(5) and F(6).

flowchart LR a((0))---b((1))---c((1))---d((2))---e((3))---f((5))---g((8))-->h((...))

Leetcode 509. Fibonacci Number

Top-down (with memoization)

class Solution:
    def fib(self, n: int, memo: dict = None) -> int:
        """
            T: O(N)
            S: O(N)
        """
        if memo is None:
            memo = dict()

        if n == 0:
            return 0
        elif n == 1:
            return 1
        elif n in memo:
            # Overlapping subproblems
            return memo[n]
        else:
            # Optimal substructure
            memo[n] = self.fib(n - 1) + self.fib(n - 2)
            return memo[n]

Bottom up (with tabulation)

class Solution:
    def fib(self, n: int) -> int:
        """
            T: O(N)
            S: O(N)
        """
        if n == 0:
            # Return 0 if n = 0
            return 0
        else:
            # Since we need to use "n" as an index,
            # we will create an array for length n+1
            dp = [0] * (n + 1)
            dp[1] = 1

            # dp[i=n] == dp[-1] 
            for i in range(2, n + 1):
                dp[i] = dp[i - 1] + dp[i - 2]
            
            return dp[-1]