Skip to main content

Introduction

  • It is an optimization over plain recursion
  • The idea is to reuse the solution of subproblem when they are overlapping
  • 2 ways to implement:
    • Memoization (Top Down)
    • Tabulation (Bottom Up)
  • Applications: Bellman Ford Algo, Floyd Warshall Algo

Pseudo Code:

def fibonacci(n):
    if n == 0 or n == 1:
        return n
    return fibonacci(n-1) + fibonacci(n - 2)

Suppose we call fibonacci(5)
At line 4: fibonacci(4) + fibonacci(3)
fibonacci(4) will again call for fibonacci(3)
Hence we will have to calculate fibonacci(3) twice


Memoization​

dp = [None] * 100
def fibonacci(n):
    if dp[n] != None:
        return dp[n]
    if n == 0 or n == 1:
        dp[n] = n
    else:
        dp[n] = fibonacci(n - 1) + fibonacci(n - 2)
    return dp[n]

Tabulation​

def fibonacci(n):
    dp = [None] * (n + 1)
    dp[0] = 0
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]