Here's the space-improved Fibonacci:
plaintext function fib(n) if n ≤ 1 1 then return n prev2 := 0 prev1 := 1 for i from 2 to n current := prev1 + prev2 prev2 := prev1 prev1 := current return prev1
Use two variables instead of an array. computes the next Fibonacci number and updates your "window." Time: O(n), space: O(1).
Let's see your process: You started with code that would run for years and used so much memory. Now you have code that runs in microseconds using two variables. Same problem and same answer, but completely different performance.
This is what DP gives you: the ability to see waste and eliminate it.