Fibonacci Series

Your first concrete DP power-up

Now that we've covered Introduction to Dynamic Programming, you already know the core signals: repeated work, optimal substructure, memoization, and tabulation.

The Fibonacci series is the cleanest arena to practice those ideas without distraction. It is small enough to trace by hand, but it exposes the exact performance trap that DP solves.

Think of this lesson like the first training arc in a shonen anime: the technique looks simple, but mastering the form prepares you for tougher battles later, like sequence alignment and constrained optimization.

Fibonacci as a recurrence

The Fibonacci numbers are defined as:

• fib(0) = 0
• fib(1) = 1
• fib(n) = fib(n - 1) + fib(n - 2) for n >= 2

That recurrence translates naturally into recursion. But as you saw in the previous lesson's repeated-work demo, natural recursion can secretly redo the same subproblems many times.

Let's count how many function calls a naive version makes.

```python
calls = 0

def fib_naive(n):
    global calls
    calls += 1

    if n <= 1:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)

for n in range(8):
    calls = 0
    value = fib_naive(n)
    print(f'fib({n}) = {value}, calls = {calls}')
```

When computing fib(6) with naive recursion, which subproblem is likely computed more than once?

Cache each subproblem once

Memoization keeps the recursive shape but adds a cache. The first time we compute fib(k), we store it. Later calls reuse the stored value.

This is the same memoization cache idea from Introduction to Dynamic Programming, now applied to a real recurrence.

Result: each fib(k) for 0 <= k <= n is solved once.

```python
def fib_memo(n, memo=None):
    if memo is None:
        memo = {}

    if n in memo:
        return memo[n]

    if n <= 1:
        memo[n] = n
    else:
        memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)

    return memo[n]

n = 10
print(f'fib({n}) = {fib_memo(n)}')
print('First 11 Fibonacci numbers:')
print([fib_memo(i) for i in range(11)])
```

True or false: memoized Fibonacci still has exponential time complexity because it uses recursion.

Tabulation builds from the base cases

Memoization starts at fib(n) and recursively asks for smaller answers.

Tabulation goes the other direction:

fib(0)  fib(1)  fib(2)  fib(3)  fib(4)  fib(5)
  0       1       1       2       3       5

Each cell depends only on the two previous cells:

dp[i] = dp[i - 1] + dp[i - 2]

This is the tabulation mindset from the previous lesson, now made concrete.

Fill in the blank with the standard Fibonacci base-case value:

fib(1) = ____

Iterative Fibonacci with a table

Here is the bottom-up version. We create a table where dp[i] stores the answer to the subproblem fib(i).

This version avoids recursion entirely, which also avoids Python recursion-depth concerns for larger n.

```python
def fib_tab(n):
    if n <= 1:
        return n

    dp = [0] * (n + 1)
    dp[0] = 0
    dp[1] = 1

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

    print('DP table:', dp)
    return dp[n]

n = 10
print(f'fib({n}) = {fib_tab(n)}')
```

Which statement best compares memoization and tabulation for Fibonacci?

Do we need the whole table?

For Fibonacci, dp[i] only depends on two previous values. That means we can compress space from O(n) to O(1).

This is a common DP optimization pattern: first write the clear table version, then ask which past states are truly needed.

For Fibonacci, the answer is just two numbers.

```python
def fib_space_optimized(n):
    if n <= 1:
        return n

    prev2 = 0  # fib(0)
    prev1 = 1  # fib(1)

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

    return prev1

for n in [0, 1, 2, 5, 10, 20]:
    print(f'fib({n}) = {fib_space_optimized(n)}')
```

What you should keep

Fibonacci is simple, but it contains the DP pattern in miniature:

• Define the state: fib(i)
• Identify base cases: fib(0), fib(1)
• Write the transition: fib(i) = fib(i - 1) + fib(i - 2)
• Avoid repeated work with memoization or tabulation
• Optimize space when only a small window of states is needed

In the next lesson, we'll move from one-dimensional numeric states to comparing sequences, where the same DP instincts become much more powerful.