Dynamic Programming (Fibonacci) Algorithm Tutorial

Dynamic Programming: Memoization

Dynamic Programming (DP) is an optimization technique that solves complex problems by breaking them into overlapping subproblems and storing results to avoid redundant computation. DP is also known as "memoization" when applied top-down.

You have two approaches. With top-down memoization, you add a cache to your recursion. With bottom-up tabulation, you build answers iteratively from base cases.

Top-down with memoization:

memo = {}
function fib(n):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib(n - 1) + fib(n - 2)
    return memo[n]

Bottom-up tabulation:

function fib(n):
    if n <= 1:
        return n
    dp = array of size n + 1
    dp[0] = 0
    dp[1] = 1
    for i from 2 to n:
        dp[i] = (dp[i-1] + dp[i-2]) mod (10^9 + 7)
    return dp[n]

You transform $O(2^n)$ into $O(n)$ by eliminating redundant calculations.

Applications: You use DP for optimization problems, counting problems, string matching, and shortest path algorithms.

Time complexity: $O(n)$ because you compute each value once.

Space complexity: $O(n)$ for the DP array. You can optimize to $O(1)$ by keeping only the last $2$ values.