7a:T518,/** * Memoized Fibonacci (Top-Down DP) * * Time Complexity: O(n) — each subproblem solved exactly once * Space Complexity: O(n) — memo array + O(n) call stack * * This approach keeps the intuitive recursive structure while * eliminating all redundant computation through caching. */ function fibonacciMemoized(n: number, memo: Map = new Map()): number { // Base cases if (n <= 1) { return n; } // Check if already computed if (memo.has(n)) { return memo.get(n)!; // Cache hit — return immediately } // Compute and store before returning const result = fibonacciMemoized(n - 1, memo) + fibonacciMemoized(n - 2, memo); memo.set(n, result); return result; } // Alternative using an array (often faster for dense integer keys) function fibonacciMemoArray(n: number, memo: number[] = []): number { if (n <= 1) return n; if (memo[n] !== undefined) { return memo[n]; } memo[n] = fibonacciMemoArray(n - 1, memo) + fibonacciMemoArray(n - 2, memo); return memo[n]; } // Now F(50) computes instantly instead of taking years console.log(fibonacciMemoized(50)); // Output: 12586269025 console.log(fibonacciMemoized(100)); // Output: 354224848179261915075n (needs BigInt)7b:T425,/** * Tabulated Fibonacci (Bottom-Up DP) * * Time Complexity: O(n) — single pass through the array * Space Complexity: O(n) — the dp table * * This approach eliminates recursion entirely, building solutions * from the smallest subproblems upward. */ function fibonacciTabulated(n: number): number { // Handle base cases if (n <= 1) return n; // Create DP table with space for F(0) through F(n) const dp: number[] = new Array(n + 1); // Initialize base cases dp[0] = 0; dp[1] = 1; // Fill the table in order of increasing index // This guarantees dependencies are satisfied: dp[i-1] and dp[i-2] exist for (let i = 2; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 2]; } // The answer is at the final position return dp[n]; } // Visualization of the table being filled: // i: 0 1 2 3 4 5 6 7 8 9 10 // dp: 0 1 1 2 3 5 8 13 21 34 55 console.log(fibonacciTabulated(10)); // Output: 55 console.log(fibonacciTabulated(50)); // Output: 125862690257c:T4af,/** * Space-Optimized Fibonacci * * Time Complexity: O(n) * Space Complexity: O(1) — only three variables regardless of n * * The key insight: F(i) only depends on F(i-1) and F(i-2). * We don't need to remember earlier values. */ function fibonacciOptimized(n: number): number { if (n <= 1) return n; // Only track the last two Fibonacci numbers let prev2 = 0; // F(i-2), starts as F(0) let prev1 = 1; // F(i-1), starts as F(1) for (let i = 2; i <= n; i++) { // Compute current Fibonacci number const current = prev1 + prev2; // Slide the window: what was prev1 becomes prev2 // and current becomes the new prev1 prev2 = prev1; prev1 = current; } // After the loop, prev1 contains F(n) return prev1; } // Alternative with destructuring (more elegant, same logic) function fibonacciOptimizedAlt(n: number): number { if (n <= 1) return n; let [a, b] = [0, 1]; for (let i = 2; i <= n; i++) { [a, b] = [b, a + b]; } return b; } // Works efficiently for any n without memory concerns console.log(fibonacciOptimized(100)); // Works instantly7d:Td1c,/** * Production-Quality Fibonacci Calculator * * Handles edge cases, provides multiple interfaces, and manages * integer overflow using BigInt when necessary. */ class FibonacciCalculator { /** * Compute the nth Fibonacci number. * * @param n - The index (0-indexed) of the Fibonacci number to compute. * n must be a non-negative integer. * @returns The nth Fibonacci number as a BigInt (safe for large n). * @throws Error if n is negative or not an integer. * * Time Complexity: O(n) * Space Complexity: O(1) * * @example * FibonacciCalculator.compute(10) // Returns 55n * FibonacciCalculator.compute(100) // Returns 354224848179261915075n */ static compute(n: number): bigint { // Input validation if (!Number.isInteger(n) || n < 0) { throw new Error(`Invalid input: n must be a non-negative integer, got ${n}`); } // Base cases if (n === 0) return 0n; if (n === 1) return 1n; // Space-optimized computation using BigInt for arbitrary precision let prev2 = 0n; let prev1 = 1n; for (let i = 2; i <= n; i++) { const current = prev1 + prev2; prev2 = prev1; prev1 = current; } return prev1; } /** * Compute a range of Fibonacci numbers. * Efficient when multiple values are needed. */ static computeRange(start: number, end: number): bigint[] { if (start < 0 || end < start) { throw new Error(`Invalid range: [${start}, ${end}]`); } const result: bigint[] = []; let prev2 = 0n; let prev1 = 1n; for (let i = 0; i <= end; i++) { const current = i <= 1 ? BigInt(i) : prev1 + prev2; if (i >= start) { result.push(i <= 1 ? BigInt(i) : current); } if (i >= 1) { prev2 = prev1; prev1 = current; } } return result; } /** * Check if a number is a Fibonacci number. * A number is Fibonacci iff 5n² ± 4 is a perfect square. */ static isFibonacci(num: bigint): boolean { if (num < 0n) return false; const isPerfectSquare = (n: bigint): boolean => { if (n < 0n) return false; const sqrt = this.bigIntSqrt(n); return sqrt * sqrt === n; }; const test1 = 5n * num * num + 4n; const test2 = 5n * num * num - 4n; return isPerfectSquare(test1) || isPerfectSquare(test2); } private static bigIntSqrt(n: bigint): bigint { if (n < 0n) throw new Error("Square root of negative number"); if (n === 0n) return 0n; let x = n; let y = (x + 1n) / 2n; while (y < x) { x = y; y = (x + n / x) / 2n; } return x; } } // Usage examples console.log(FibonacciCalculator.compute(50)); // 12586269025n console.log(FibonacciCalculator.computeRange(0, 10)); // [0n, 1n, 1n, 2n, ...] console.log(FibonacciCalculator.isFibonacci(55n)); // true console.log(FibonacciCalculator.isFibonacci(56n)); // false72:{"json":{"id":"seed_378b20c222a7f88fdaae270b22c417b7","slug":"1d-dp-problems","category":"Data Structures & Algorithms","topic":"1D DP Problems — Fibonacci & Climbing Stairs","title":"1D DP Problems — Fibonacci & Climbing Stairs","description":"Master one-dimensional dynamic programming through the classic problems: Fibonacci sequence, climbing stairs, and house robber. Learn to identify single-index state representation, build intuition for state transitions, and optimize space complexity in linear DP problems.","difficulty":"INTERMEDIATE","estimatedMinutes":75,"pages":[{"id":"seed_9bd3e65138e9c5186f8d51dcdb59f499","title":"Fibonacci Sequence as DP","order":0,"content":[{"id":"opening-gateway","title":"The Gateway to Dynamic Programming","content":[{"data":{"content":"If there is one problem that serves as the universal introduction to dynamic programming, it is computing the Fibonacci sequence. This isn't because Fibonacci is particularly practical — in real-world applications, you'll rarely need the 50th Fibonacci number. Its value lies in its **pedagogical clarity**: the Fibonacci sequence perfectly illustrates every core DP concept with minimal complexity.\n\nThe Fibonacci sequence is defined mathematically as:\n\n> **F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2) for n ≥ 2**\n\nThis yields the sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...\n\nAt first glance, this seems trivially simple — just add the previous two numbers. But when you try to compute F(n) directly from this recursive definition, you encounter a phenomenon that exposes the fundamental inefficiency that dynamic programming exists to solve: **exponential redundant computation**."},"type":"text"},{"data":{"icon":"Target","title":"What You Will Learn","content":"By the end of this page, you will understand: (1) Why naive recursion fails catastrophically for Fibonacci, (2) How overlapping subproblems manifest in the recursion tree, (3) How memoization eliminates redundancy with O(n) time and O(n) space, (4) How tabulation achieves the same with iterative bottom-up construction, (5) How space optimization reduces to O(1) memory, and (6) Why Fibonacci is the canonical DP teaching example.","variant":"info"},"type":"callout"}]},{"id":"mathematical-origins","title":"Mathematical Origins and Properties","content":[{"data":{"content":"The Fibonacci sequence, named after the Italian mathematician Leonardo of Pisa (c. 1170–1250), also known as Fibonacci, was first introduced to Western mathematics in his 1202 book *Liber Abaci*. The problem he posed was deceptively simple:\n\n> *Suppose a pair of rabbits produce one new pair every month, and each new pair becomes fertile after one month. Starting with one pair, how many pairs will there be after n months?*\n\nThis biological puzzle encodes a recurrence relation that appears throughout nature—in spiral patterns of shells, the arrangement of leaves, branching in trees, and even financial markets."},"type":"text"},{"data":{"items":["**Base Cases**: F(0) = 0 and F(1) = 1 — Every Fibonacci sequence starts from the same foundation.","**Recurrence Relation**: F(n) = F(n-1) + F(n-2) — Each term depends on exactly two preceding terms.","**Exponential Growth**: F(n) ≈ φⁿ/√5, where φ = (1+√5)/2 ≈ 1.618 (the golden ratio).","**Consecutive Ratio Limit**: lim(n→∞) F(n+1)/F(n) = φ — Successive ratios converge to the golden ratio.","**Closed-Form (Binet's Formula)**: F(n) = (φⁿ - ψⁿ)/√5, where ψ = (1-√5)/2."],"title":{"icon":"Sparkles","text":"Key Mathematical Properties of Fibonacci","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"content":"**Why does this matter for DP?**\n\nThe Fibonacci recurrence relation has a critical property: **each subproblem depends on exactly two smaller subproblems**. This creates a clean, tree-structured dependency graph with substantial overlap. As we'll see, naive recursion computes the same values exponentially many times, while DP ensures each value is computed exactly once."},"type":"text"},{"data":{"icon":"Info","title":"Binet's Formula: Why We Still Need DP","content":"Binet's closed-form formula allows computing F(n) directly in O(1) time with matrix exponentiation or even O(1) with floating point — but floating-point precision fails for large n. Even for moderate values like n=70, floating-point errors accumulate. DP provides exact integer arithmetic, making it essential for many practical computations.","variant":"note"},"type":"callout"}],"titleType":"number","titleNumber":1},{"id":"naive-recursive-solution","title":"The Naive Recursive Solution","content":[{"data":{"content":"The most straightforward way to compute Fibonacci numbers is to directly translate the mathematical definition into code. This approach, while elegant in its simplicity, harbors a devastating inefficiency.\n\nLet's examine the naive recursive implementation:"},"type":"text"},{"data":{"code":"/**\n * Naive Recursive Fibonacci\n * \n * Time Complexity: O(2^n) — exponential\n * Space Complexity: O(n) — recursive call stack depth\n * \n * WARNING: This is deliberately inefficient for educational purposes.\n * Do NOT use this in production code.\n */\nfunction fibonacciNaive(n: number): number {\n // Base cases: F(0) = 0, F(1) = 1\n if (n <= 1) {\n return n;\n }\n \n // Recursive case: F(n) = F(n-1) + F(n-2)\n // This innocent-looking line causes exponential explosion\n return fibonacciNaive(n - 1) + fibonacciNaive(n - 2);\n}\n\n// Test the function\nconsole.log(fibonacciNaive(10)); // Output: 55\nconsole.log(fibonacciNaive(20)); // Output: 6765\nconsole.log(fibonacciNaive(40)); // WARNING: Takes several seconds!\nconsole.log(fibonacciNaive(50)); // DANGER: May hang your system!","title":"Naive Recursive Fibonacci — O(2ⁿ) Time Complexity","language":"typescript"},"type":"code"},{"data":{"content":"**Why does this simple code become catastrophically slow?**\n\nThe problem isn't the recursion itself — it's the **redundant computation**. Each call to `fibonacciNaive(n)` spawns two more calls, and those calls spawn four more, and so on. The result is an exponentially growing tree of function calls.\n\nTo understand the magnitude of this inefficiency, let's count exactly how many times each subproblem is computed:"},"type":"text"},{"data":{"rows":[["F(0)","34 times","4,181 times","~63 million times"],["F(1)","55 times","6,765 times","~102 million times"],["F(5)","8 times","610 times","~6.3 million times"],["F(10)","1 time","55 times","~102,334 times"],["Total calls","177","21,891","~331 million"]],"caption":"Redundant Computation in Naive Fibonacci","headers":["Subproblem","Times Computed for F(10)","Times Computed for F(20)","Times Computed for F(40)"]},"type":"table"},{"data":{"icon":"AlertCircle","title":"The Exponential Explosion","content":"For F(40), the naive algorithm makes approximately 331 million function calls. For F(50), it's over 40 billion. For F(100), it would take longer than the age of the universe on any computer. This is the cost of not recognizing overlapping subproblems.","variant":"warning"},"type":"callout"}],"titleType":"number","titleNumber":2},{"id":"visualizing-problem-tree","title":"Visualizing the Recursion Tree","content":[{"data":{"content":"To truly understand why naive recursion fails, we must visualize the **recursion tree**. This tree shows every function call as a node, with child nodes representing the recursive calls made by each invocation.\n\nLet's trace through computing F(6) with naive recursion:"},"type":"text"},{"data":{"code":" F(6)\n / \\\n F(5) F(4)\n / \\ / \\\n F(4) F(3) F(3) F(2)\n / \\ / \\ / \\ / \\\n F(3) F(2) F(2) F(1) F(2) F(1) F(1) F(0)\n / \\ / \\ / \\ / \\\n F(2) F(1) ... ... ... F(1) F(0)\n / \\\n F(1) F(0)\n\nTotal nodes: 25 for computing just F(6)\nEach node represents one function call with its own stack frame.\n\nREDUNDANT COMPUTATIONS:\n- F(4) is computed 2 times\n- F(3) is computed 3 times\n- F(2) is computed 5 times\n- F(1) is computed 8 times (appears at leaves)\n- F(0) is computed 5 times (appears at leaves)","title":"Recursion Tree for F(6) — Naive Approach","language":"plaintext"},"type":"code"},{"data":{"content":"**The critical insight:**\n\nNotice how F(4) appears twice as a completely separate subtree. The algorithm doesn't remember that it already computed F(4) = 3 on the left side — it recomputes the entire subtree from scratch on the right side. This duplication cascades: F(3) appears three times, F(2) appears five times, and so on.\n\nThis is the defining characteristic of **overlapping subproblems**: the same computational work is performed multiple times because the recursive structure doesn't preserve results."},"type":"text"},{"data":{"items":["**Tree Height**: For F(n), the tree has height n (deepest path goes F(n) → F(n-1) → ... → F(1) → F(0)).","**Branching Factor**: Each non-leaf node has exactly 2 children.","**Approximate Nodes**: The tree has approximately F(n+1) leaves and 2·F(n+1) - 1 total nodes.","**Time Complexity**: Since F(n) ≈ φⁿ/√5, the number of operations is O(φⁿ) ≈ O(1.618ⁿ) ≈ O(2ⁿ).","**Practical Limit**: On a modern computer performing 10⁹ operations/second, F(45) takes ~1 second, F(50) takes ~1 minute, F(60) takes ~18 hours."],"title":{"icon":"TrendingUp","text":"Growth Analysis of Recursion Tree","type":"icon","color":"destructive","variant":"outline-circle"},"variant":"glass"},"type":"list"},{"data":{"icon":"Lightbulb","title":"The DP Revelation","content":"What if we could remember results? If after computing F(4) once, we stored the result and simply looked it up every subsequent time, we'd eliminate the redundant subtrees entirely. This is exactly what memoization provides — and it transforms O(2ⁿ) into O(n).","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":3},{"id":"memoization-top-down","title":"Memoization: Top-Down Dynamic Programming","content":[{"data":{"content":"**Memoization** is the technique of storing computed results so they can be reused instead of recalculated. In the context of Fibonacci, we add a cache (or \"memo\") that records each F(i) value the first time it's computed. On subsequent calls with the same argument, we return the cached value immediately.\n\nThis transformation is simple but profound — it converts exponential time complexity to linear."},"type":"text"},{"data":{"code":"$7a","title":"Memoized Fibonacci — O(n) Time, O(n) Space","language":"typescript"},"type":"code"},{"data":{"content":"**How memoization transforms the recursion tree:**\n\nWith memoization, the recursion tree collapses dramatically. Each unique subproblem F(i) is computed exactly once, then every subsequent reference becomes an O(1) lookup."},"type":"text"},{"data":{"code":"Call: F(6) memo: {}\n├─ Call: F(5) memo: {}\n│ ├─ Call: F(4) memo: {}\n│ │ ├─ Call: F(3) memo: {}\n│ │ │ ├─ Call: F(2) memo: {}\n│ │ │ │ ├─ Call: F(1) → return 1 (base case)\n│ │ │ │ └─ Call: F(0) → return 0 (base case)\n│ │ │ │ └─ Store: memo[2] = 1\n│ │ │ └─ Call: F(1) → return 1 (base case)\n│ │ │ └─ Store: memo[3] = 2\n│ │ └─ CACHE HIT: F(2) → return 1 memo: {2:1, 3:2}\n│ │ └─ Store: memo[4] = 3\n│ └─ CACHE HIT: F(3) → return 2 memo: {2:1, 3:2, 4:3}\n│ └─ Store: memo[5] = 5\n└─ CACHE HIT: F(4) → return 3 memo: {2:1, 3:2, 4:3, 5:5}\n└─ Store: memo[6] = 8\n\nResult: F(6) = 8\n\nTotal unique computations: 5 (F(2), F(3), F(4), F(5), F(6))\nTotal cache hits: 4 (second calls to F(2), F(3), F(4), F(1))\nTotal function calls: ~11 (vs 25 in naive approach)","title":"Execution Trace with Memoization for F(6)","language":"plaintext"},"type":"code"},{"data":{"left":[{"data":{"items":["Preserves natural recursive problem structure","Only computes needed subproblems (lazy)","Easy to convert from naive recursion","Intuitive when dependencies are complex"],"title":{"icon":"CheckCircle","text":"Advantages of Memoization","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"}],"right":[{"data":{"items":["Recursive call stack adds O(n) space overhead","Risk of stack overflow for large n","Cache lookup overhead per call","May cache unnecessary subproblems"],"title":{"icon":"AlertCircle","text":"Limitations of Memoization","type":"icon","color":"accent","variant":"outline-circle"},"variant":"glass"},"type":"list"}]},"type":"two-column"}],"titleType":"number","titleNumber":4},{"id":"tabulation-bottom-up","title":"Tabulation: Bottom-Up Dynamic Programming","content":[{"data":{"content":"**Tabulation** takes the opposite approach from memoization. Instead of starting from the top and working down with caching, we start from the base cases and build upward iteratively. We fill a table (array) with solutions to subproblems in order of increasing size, ensuring that when we need to compute F(i), we've already computed F(i-1) and F(i-2).\n\nThis eliminates recursion entirely, avoiding stack overflow risks and often improving cache efficiency."},"type":"text"},{"data":{"code":"$7b","title":"Tabulated Fibonacci — O(n) Time, O(n) Space","language":"typescript"},"type":"code"},{"data":{"content":"**Why tabulation often outperforms memoization:**\n\n1. **No recursion overhead**: Each iteration is a simple addition and array access — no function call setup/teardown.\n\n2. **Better cache locality**: We access array elements in sequential order, which modern CPUs love (prefetching, cache lines).\n\n3. **No stack overflow risk**: For n = 1,000,000, memoization might exceed stack limits. Tabulation handles any n that fits in memory.\n\n4. **Predictable memory usage**: The array size is known upfront (n+1 elements).\n\nHowever, tabulation requires us to know the **computation order** in advance — specifically, which subproblems are needed and in what sequence. For Fibonacci, this is trivial (just count upward), but for more complex problems, determining the correct order can be challenging."},"type":"text"},{"data":{"icon":"Lightbulb","title":"When to Choose Tabulation vs Memoization","content":"Use **tabulation** when: (1) All subproblems will be computed anyway, (2) The dependency order is clear and simple, (3) You need to avoid stack overflow. Use **memoization** when: (1) Many subproblems might not be needed, (2) Dependencies are complex or hard to order, (3) You want to start with the natural recursive formulation.","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":5},{"id":"space-optimization","title":"Space Optimization: Achieving O(1) Memory","content":[{"data":{"content":"A key insight elevates our Fibonacci solution from O(n) space to O(1): **we don't need the entire table, only the last two values**.\n\nAt each step, computing F(i) requires only F(i-1) and F(i-2). Once we've used F(i-2) to compute F(i), we'll never need F(i-2) again. This means we can discard old values as we progress, maintaining only a constant amount of state."},"type":"text"},{"data":{"code":"$7c","title":"Space-Optimized Fibonacci — O(n) Time, O(1) Space","language":"typescript"},"type":"code"},{"data":{"content":"**Evolution of our Fibonacci solutions:**"},"type":"text"},{"data":{"rows":[["Naive Recursion","O(2ⁿ)","O(n) stack","~45","Simplest code"],["Memoization","O(n)","O(n) cache + O(n) stack","~10,000 (stack limit)","Natural structure preserved"],["Tabulation","O(n)","O(n) array","~10⁸ (memory limit)","No stack overflow"],["Space-Optimized","O(n)","O(1)","Unlimited (integer limits only)","Minimal memory footprint"]],"caption":"Fibonacci Implementation Comparison","headers":["Approach","Time Complexity","Space Complexity","Max Practical n","Key Advantage"]},"type":"table"},{"data":{"icon":"Sparkles","title":"The Space Optimization Pattern","content":"This O(n) → O(1) space reduction is a recurring pattern in DP: when the recurrence only looks back a fixed number of steps, maintain a 'sliding window' of just those values. We'll see this pattern repeatedly in climbing stairs, house robber, and many other 1D DP problems.","variant":"success"},"type":"callout"}],"titleType":"number","titleNumber":6},{"id":"complete-implementation","title":"Complete Implementation with Edge Cases","content":[{"data":{"content":"A production-quality Fibonacci implementation must handle edge cases, potential integer overflow, and provide clear documentation. Here's a comprehensive implementation:"},"type":"text"},{"data":{"code":"$7d","title":"Production-Quality Fibonacci Implementation","language":"typescript"},"type":"code"}],"titleType":"number","titleNumber":7},{"id":"canonical-example","title":"Why Fibonacci is the Canonical DP Example","content":[{"data":{"content":"The Fibonacci sequence isn't chosen for its practical value — it's chosen because it's the **simplest possible problem that exhibits all core DP characteristics**:"},"type":"text"},{"data":{"type":"ordered","items":["**Minimal State**: A single integer index — you only need to know 'n' to define the subproblem F(n).","**Simple Recurrence**: F(n) = F(n-1) + F(n-2) — the simplest possible non-trivial combination of subproblems.","**Obvious Overlap**: F(n-1) and F(n-2) clearly share the subproblem F(n-2). The overlap is visible and intuitive.","**Clear Base Cases**: F(0) = 0 and F(1) = 1 are unambiguous termination conditions.","**Easy Visualization**: The recursion tree for F(6) fits on a whiteboard. You can trace every call.","**Dramatic Improvement**: The jump from O(2ⁿ) to O(n) is visually striking — F(50) goes from 'taking years' to 'instant'.","**Space Optimization Possible**: The reduction from O(n) to O(1) space introduces the 'sliding window' concept cleanly."],"title":{"icon":"Sparkles","text":"Why Fibonacci is Pedagogically Perfect","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"content":"**The mental model Fibonacci teaches:**\n\nAfter fully understanding Fibonacci as DP, you have internalized the fundamental questions for any DP problem:\n\n1. **What defines a subproblem?** (For Fibonacci: the index n)\n2. **What is the recurrence?** (For Fibonacci: F(n) = F(n-1) + F(n-2))\n3. **What are the base cases?** (For Fibonacci: F(0) = 0, F(1) = 1)\n4. **Do subproblems overlap?** (For Fibonacci: Yes, dramatically)\n5. **What is the computation order?** (For Fibonacci: Increasing index 0, 1, 2, ...)\n6. **Can we reduce space?** (For Fibonacci: Yes, to O(1))\n\nEvery DP problem you'll ever encounter is just a more complex version of Fibonacci. The core structure remains the same."},"type":"text"},{"data":{"icon":"Lightbulb","title":"From Fibonacci to Everything Else","content":"Once you've truly mastered Fibonacci, you've mastered the DP paradigm. Climbing stairs is Fibonacci in disguise. House robber is Fibonacci with a choice. Coin change is multi-branch Fibonacci. Every 1D DP problem is a variation on this theme.","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":8},{"id":"summary-takeaways","title":"Summary and Key Takeaways","content":[{"data":{"content":"We've explored the Fibonacci sequence as the gateway problem to dynamic programming, tracing its evolution from naive recursion to optimal solution:"},"type":"text"},{"data":{"type":"ordered","items":["**Naive recursion fails catastrophically** — O(2ⁿ) time due to exponentially redundant computation of the same subproblems.","**Overlapping subproblems are the key insight** — F(n-1) and F(n-2) share F(n-2), creating massive redundancy in the recursion tree.","**Memoization (top-down DP)** — Cache results to eliminate redundancy. Keeps recursive structure, achieves O(n) time and O(n) space.","**Tabulation (bottom-up DP)** — Fill a table iteratively from base cases. No recursion overhead, same complexity.","**Space optimization** — Since only F(i-1) and F(i-2) are needed, reduce to O(1) space with a sliding window.","**Fibonacci teaches the DP paradigm** — State definition, recurrence, base cases, overlap recognition, computation order, and space optimization."],"title":{"icon":"CheckCircle","text":"Key Takeaways","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"icon":"CheckCircle","title":"Page Complete","content":"You now have a deep understanding of Fibonacci as the canonical introduction to dynamic programming. The next page extends these concepts to the Climbing Stairs problem — a disguised Fibonacci problem that introduces the idea of 'decisions' in DP.","variant":"success"},"type":"callout"}],"titleType":"number","titleNumber":9}],"isLocked":false},{"id":"seed_4e828544417c0056941a42bd7a294f4a","title":"Climbing Stairs Variations","order":1,"content":null,"isLocked":true},{"id":"seed_8620b9de48a351a36de561d2b76179d1","title":"House Robber Problem","order":2,"content":null,"isLocked":true},{"id":"seed_c36652009be05e2b34ba274f278cea25","title":"State: Single Index — The Unifying Framework","order":3,"content":null,"isLocked":true}]}}