Dynamic Programming - Fibonacci Sequence

"""
Dynamic Programming (DP) is a method for solving complex problems by breaking them down into simpler subproblems. It is used when a problem has overlapping subproblems and optimal substructure, meaning the problem can be broken down into smaller, reusable problems, and the optimal solution can be constructed from the optimal solutions of its subproblems.

People use the terms "top-down DP" and "bottom-up DP" when better terms would be "recursive DP" and "iterative DP".

A classic example of DP is solving the Fibonacci sequence, where each number is the sum of the two preceding ones, starting from 0 and 1. That is:

fibonacci(0) = 0
fibonacci(1) = 1
fibonacci(n) = fibonacci(n-1) + fibonacci(n-2) for n > 1

With the dynamic programming approach below, instead of computing the Fibonacci sequence recursively and recalculating the same values multiple times, we store (or "memoize") previously calculated Fibonacci numbers in an array (fib_cache). This way, each Fibonacci number is calculated once, and subsequent requests for that number are answered in constant time. This method significantly reduces the time complexity from exponential in naive recursion to linear with DP.

Pseudocode:

dp(target):
    # handle edge cases
    # initialize cache
    # iteratively fill out cache up to the target
    # return cache value for target

# Mistakes I've made
- I wasn't sure how far the iteration should extend / what the first and indices represented (the 0th Fibonacci number or the 1st?). I had the iteration extend to to n-1 ("range(2, n)") when it should've extended to n (so, "range(2, n+1)").
   - Happened to me 2024.09.04
   - I think the solution is to say to yourself explicitly, "the list indices represent the ith fibonacci number, so we need to return the value when i = n. So the final return value needs to be memo[n]. So the iteration needs to end at n+1".

# Goals when reviewing this topic:
- I think maybe memorizing the pseudocode pattern is more important than memorizing the fibonacci example.
- I think it may be a good idea to try to memorize what this pattern can look like in different contexts rather than simply memorizing the simple fibonacci example.
"""

def fibonacci(n):
    if n <= 1:
        return n
    memo = [0, 1]
    for i in range(2, n + 1):
        memo.append(memo[i-1] + memo[i-2])
    return memo[n]

print(fibonacci(10))  # Output should be 55