Logo AnimGAnimG

Dynamic Programming — Fibonacci & Memoization

Pubblico: Software EngineerCategoria: Computer Science

Descrizione

Contrasts three approaches to computing Fibonacci numbers: naive recursion (exponential, showing repeated subproblems in red), top-down memoization (cached calls return instantly in green), and bottom-up DP table filling. Complexity labels O(2^n) vs O(n) are displayed prominently.

Ispirato da questa animazione?

Dynamic Programming — Fibonacci & Memoization

Description

Contrasts three approaches to computing Fibonacci numbers: naive recursion (exponential, showing repeated subproblems in red), top-down memoization (cached calls return instantly in green), and bottom-up DP table filling. Complexity labels O(2^n) vs O(n) are displayed prominently.

Phases

# Phase Name Duration Description
1 Intro 3s Title displayed
2 Naive Recursion 14s Call tree for fib(5) shown; duplicate subtrees highlighted red
3 Memoization 12s Same tree with cache table; duplicate calls return from cache (green flash)
4 Bottom-up DP 12s DP table [0,1,1,2,3,5,...] filled left to right with arrows showing dependencies
5 Complexity Comparison 6s O(2^n) vs O(n) displayed side by side
6 Outro 5s Final DP table stays visible

Layout

+--------------------------------------------------+
|  Title: Dynamic Programming                      |
+--------------------------------------------------+
|                                                  |
|  Phase 2/3: Call tree                            |
|         fib(5)                                   |
|        /       \                                 |
|    fib(4)      fib(3)                            |
|    /    \      /    \                            |
| fib(3) fib(2) fib(2) fib(1)                      |
|  ...                                             |
|  [red] = repeated subproblem                     |
|                                                  |
|  Phase 4: DP table                               |
|  [0][1][1][2][3][5][8][13]...                    |
|                                                  |
|  Complexity (bottom-right):                      |
|  Naive: O(2^n)   DP: O(n)                        |
+--------------------------------------------------+

Area Descriptions

  • Center: Call tree or DP table depending on phase
  • Bottom right: Complexity comparison box

Assets & Dependencies

  • Fonts: LaTeX / sans-serif
  • Manim version: ManimCE 0.19.1

Notes

  • Repeated subproblems in call tree highlighted with red border and fill
  • Memoized lookups show a flash effect and a green "cached" label
  • DP table arrows show which previous cells contribute to current cell