1. Fibonacci Series

Fibonacci Number¶

1. Recursion + Memoization - Top Down approach¶

In [1]:

def fib_memo(n, dp):
    """
    # 0, 1, 2, 3, 4, 5, 6, 7,  8
    # 0, 1, 1, 2, 3, 5, 8, 13, 21
    """

    # base case
    if n == 0 or n == 1:
        return n

    if dp[n] != -1:
        return dp[n]

    # recurrence relation
    dp[n] = fib_memo(n - 1, dp) + fib_memo(n - 2, dp)

    return dp[n]

def fib_memo(n, dp): """ # 0, 1, 2, 3, 4, 5, 6, 7, 8 # 0, 1, 1, 2, 3, 5, 8, 13, 21 """ # base case if n == 0 or n == 1: return n if dp[n] != -1: return dp[n] # recurrence relation dp[n] = fib_memo(n - 1, dp) + fib_memo(n - 2, dp) return dp[n]

In [2]:

n = 100
dp = [-1] * (n + 1)
ans = fib_memo(n, dp)
print(ans)

n = 100 dp = [-1] * (n + 1) ans = fib_memo(n, dp) print(ans)

354224848179261915075

In [3]:

def fib_memo(n):

    """
    # 0, 1, 2, 3, 4, 5, 6, 7,  8
    # 0, 1, 1, 2, 3, 5, 8, 13, 21
    """

    # 1. Create a 1D dp array
    dp = [-1] * (n + 1)

    def solve(n):

        # 1. base case
        if n == 0 or n == 1:
            return n

        # 3. check dp array for result before
        # making a recursive call
        if dp[n] != -1:
            return dp[n]

        # 2. Recursive relation + store result in the dp array
        dp[n] = solve(n - 1) + solve(n - 2)

        return dp[n]

    ans = solve(n)

    return ans

def fib_memo(n): """ # 0, 1, 2, 3, 4, 5, 6, 7, 8 # 0, 1, 1, 2, 3, 5, 8, 13, 21 """ # 1. Create a 1D dp array dp = [-1] * (n + 1) def solve(n): # 1. base case if n == 0 or n == 1: return n # 3. check dp array for result before # making a recursive call if dp[n] != -1: return dp[n] # 2. Recursive relation + store result in the dp array dp[n] = solve(n - 1) + solve(n - 2) return dp[n] ans = solve(n) return ans

In [4]:

n = 100
fib_memo(n)

n = 100 fib_memo(n)

Out[4]:

354224848179261915075

2. Tabulation - Bottom Up approach¶

In [5]:

def fib_tab(n, dp):
    """
    # 0, 1, 2, 3, 4, 5, 6, 7,  8
    # 0, 1, 1, 2, 3, 5, 8, 13, 21
    """

    # base case
    if n <= 1:
        return n

    # processing
    # check if you already have the number in dp
    if dp[n] != -1:
        return dp[n]

    # go for bottom-up tabulation
    # using the recurrence relation
    # dp[n] = dp[n-1] + dp[n-2]

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

    return dp[n]

def fib_tab(n, dp): """ # 0, 1, 2, 3, 4, 5, 6, 7, 8 # 0, 1, 1, 2, 3, 5, 8, 13, 21 """ # base case if n <= 1: return n # processing # check if you already have the number in dp if dp[n] != -1: return dp[n] # go for bottom-up tabulation # using the recurrence relation # dp[n] = dp[n-1] + dp[n-2] for i in range(2, n + 1): dp[i] = dp[i - 1] + dp[i - 2] return dp[n]

In [6]:

n = 100

# step-1: define dp array
dp = [-1] * (n + 1)

# step-2: fill this using the base case
dp[0] = 0
dp[1] = 1


ans = fib_tab(n, dp)
print(ans)

n = 100 # step-1: define dp array dp = [-1] * (n + 1) # step-2: fill this using the base case dp[0] = 0 dp[1] = 1 ans = fib_tab(n, dp) print(ans)

354224848179261915075

In [7]:

def fib_tab(n):

    if n <= 1:
        return n

    # 1. create a 1D dp array
    dp = [-1] * (n + 1)

    # 2. base case(s)
    dp[0] = 0
    dp[1] = 1

    # this is not needed
    # as we are building our solution bottom-up
    # if dp[n] != -1:
    #     return dp[n]

    # 3. build dp array bottom-up using for loop
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]

    return dp[n]

def fib_tab(n): if n <= 1: return n # 1. create a 1D dp array dp = [-1] * (n + 1) # 2. base case(s) dp[0] = 0 dp[1] = 1 # this is not needed # as we are building our solution bottom-up # if dp[n] != -1: # return dp[n] # 3. build dp array bottom-up using for loop for i in range(2, n + 1): dp[i] = dp[i - 1] + dp[i - 2] return dp[n]

In [8]:

fib_tab(100)

fib_tab(100)

Out[8]:

354224848179261915075

3. Space Optimization¶

In [9]:

def fib_space_opt(n):

    """
    # 0, 1, 2, 3, 4, 5, 6, 7,  8
    # 0, 1, 1, 2, 3, 5, 8, 13, 21
    """

    # base case
    if n <= 1:
        return n

    prev1 = 0
    prev2 = 1

    for i in range(2, n + 1):
        current = prev1 + prev2

        # shift
        prev1 = prev2
        prev2 = current

        # print(f"current: {current}")
        # print(f"prev1: {prev1}")
        # print(f"prev2: {prev2}")
        # print()

    return current

def fib_space_opt(n): """ # 0, 1, 2, 3, 4, 5, 6, 7, 8 # 0, 1, 1, 2, 3, 5, 8, 13, 21 """ # base case if n <= 1: return n prev1 = 0 prev2 = 1 for i in range(2, n + 1): current = prev1 + prev2 # shift prev1 = prev2 prev2 = current # print(f"current: {current}") # print(f"prev1: {prev1}") # print(f"prev2: {prev2}") # print() return current

In [10]:

n = 100

ans = fib_space_opt(n)
print(f"ans: {ans}")

n = 100 ans = fib_space_opt(n) print(f"ans: {ans}")

ans: 354224848179261915075

In [11]:

def fib_tab_space_opt(n):

    if n <= 1:
        return n

    prev1 = 1
    prev2 = 0

    for i in range(2, n + 1):
        current = prev1 + prev2
        prev2 = prev1
        prev1 = current

    return prev1

def fib_tab_space_opt(n): if n <= 1: return n prev1 = 1 prev2 = 0 for i in range(2, n + 1): current = prev1 + prev2 prev2 = prev1 prev1 = current return prev1

In [12]:

n = 100
fib_tab_space_opt(n)

n = 100 fib_tab_space_opt(n)

Out[12]:

354224848179261915075

In [ ]: