Dynamic programming
The conceptWhy naive Fibonacci code makes 2.7 million calls for the 30th number
Dynamic programming solves a big problem by solving smaller subproblems, saving each answer and reusing it. It only helps when the same subproblems keep coming back. These are called overlapping subproblems.
Each Fibonacci number is the sum of the two before it: 1, 1, 2, 3, 5, 8. Plain recursive code for F(30) calls F(29) and F(28), but F(29) calls F(28) again. The repeats snowball into 2,692,537 calls.
Keep a small table called a memo. Before computing F(k), check whether it is already stored. If it isn't, compute it once and save it. F(30) then needs just 30 additions.
What it’s forDefines each Fibonacci number from two smaller ones, with every result saved so it is computed only once.
F(n) = F(n−1) + F(n−2), saved in memo[n]
- F(n)
- the n-th Fibonacci number, with F(1) = F(2) = 1
- n
- which number in the sequence we want, e.g. 30
- memo[n]
- the table slot where F(n) is stored after its first computation
What it givesEach Fibonacci number in one addition, so the total work grows like n instead of about 1.6ⁿ.
- Table: F(3)=1+1=2, F(4)=2+1=3, F(5)=3+2=5
- Plain recursion for F(5): 15 calls; for F(30): 2,692,537 calls
- With the memo, F(30) takes 30 additions