The Fibonacci numbers start with 0 and 1. Every next number is the sum of the two before it, so compute F of n.
DSA Animator › DSA Revision › Dynamic Programming › Fibonacci Number
Remember: overlapping subproblems are the signal for dynamic programming. Keep only the states the next step needs. The video solves Fibonacci Number (LeetCode 509, Easy) with the 1D DP pattern from the Dynamic Programming topic, and you can replay every step in the interactive Fibonacci Number animation.
The Fibonacci numbers start with 0 and 1. Every next number is the sum of the two before it, so compute F of n.
For n equal to 6, the sequence is 0, 1, 1, 2, 3, 5, 8, so F of 6 is 8.
The direct recursion calls F of n minus 1 and F of n minus 2, and each of those calls two more. The same values are computed again and again, so the time grows like 2 to the power n. For example, F of 3 alone is computed three times while finding F of 6.
This is the core idea of dynamic programming: solve each small problem once and store the answer. Build the values from the bottom up, starting with F of 0 and F of 1. Each new value only needs the previous two. So instead of a whole array, two variables are enough.
Start with 0 and 1. 0 plus 1 gives F of 2, which is 1. 1 plus 1 gives F of 3, which is 2. 1 plus 2 gives F of 4, which is 3, and 2 plus 3 gives F of 5, which is 5. 3 plus 5 gives F of 6, which is 8. The answer is 8, found in just five additions.
In code, return n directly when n is less than 2. Keep a equal to 0 and b equal to 1. Loop from 2 to n, compute the next value as a plus b, then shift a and b forward. Return b, so it's O of n time and O of 1 space.
Remember: overlapping subproblems are the signal for dynamic programming. Keep only the states the next step needs.