DYNAMIC PROGRAMMING › 1D ARRAYS

Fibonacci DP

Fibonacci is the classic example of overlapping subproblems, making it the cleanest introduction to memoization and tabulation.

Time

O(N)

Space

O(1) or O(N)

Key Principle 1

Naive recursion repeats the same work many times.

Key Principle 2

Memoization stores previously computed values in a cache.

Key Principle 3

Tabulation builds the sequence bottom-up from the smallest terms.

Key Principle 4

The same recurrence appears in many real DP problems.

Loading Lab...

Fibonacci Dp