Fibonacci and Dynamic Programming — The Gateway DP Problem for leetcode fibonacci

Fibonacci Number (#509) is rated Easy on LeetCode. Most candidates solve it in under two minutes, mark it complete, and move on. This is one of the most costly mistakes in technical interview preparation. The mistake is not failing to solve it — the mistake is solving it only one way, in one minute, and learning nothing about why it works.

Fibonacci is the minimal example of a dynamic programming problem. It is the problem where overlapping subproblems and optimal substructure appear in their most transparent form, where the difference between exponential and linear time is visible without complex analysis, and where the leap from recursion to memoization to tabulation to space optimization can be made in a single sitting. No other LeetCode problem teaches all of this in such compact form.

Candidates who struggle with Hard DP problems — Grid Unique Paths, Longest Common Subsequence, Edit Distance, Burst Balloons — almost universally share one preparation gap: they skipped the Fibonacci lesson. They learned the DP template at the surface level without internalizing the reasoning behind it. They can apply a memo dictionary to a recursion but cannot explain why it reduces O(2^n) to O(n). They can write bottom-up tabulation but cannot articulate why working backwards from base cases is equivalent to top-down memoization.

This guide treats Fibonacci as it deserves to be treated: as the entry point to the entire DP skill tree. Section 2 presents all four solution approaches with complexity analysis. Section 3 explains why Fibonacci qualifies as a DP problem and what that classification means. Section 4 shows the problems that are structurally identical to Fibonacci — problems you will encounter in real interviews. Section 5 maps the skill ladder from Fibonacci to the most complex DP problem categories. Section 6 covers the mistakes that even well-prepared candidates make on this deceptively simple problem.

Read this guide once. Implement all four solutions. Understand the recurrence. Then solve the problems in Section 4. When you can explain the Fibonacci recurrence to a five-year-old and implement its space-optimized form in ninety seconds, you are ready to start Hard DP.

There are four distinct approaches to Fibonacci Number (#509), each representing a different level of DP understanding. Every serious candidate should be able to implement all four, explain their complexities, and articulate why each improvement works. An interviewer who asks you to optimize from your first solution to your last is walking you through the entire DP thought process — this question is a complete DP interview in miniature.

Approach 1 — Naive Recursion: The direct translation of the mathematical definition. F(n) = F(n-1) + F(n-2), with F(0) = 0 and F(1) = 1. This approach is correct but catastrophically inefficient. Time complexity: O(2^n), because each call branches into two subproblems, and the same subproblems are recomputed exponentially many times. F(5) computes F(3) twice. F(10) computes F(6) eight times. F(50) makes over a trillion function calls. Space complexity: O(n) for the call stack depth.

Approach 2 — Top-Down Memoization: Add a cache (dictionary or array) to the recursive solution. Before computing F(n), check if the result is already cached; if so, return it directly. If not, compute it, store it in the cache, and return it. This eliminates all duplicate computation. Time complexity: O(n) — each subproblem is computed exactly once. Space complexity: O(n) for the cache plus O(n) for the call stack. This is the most natural first optimization and the one candidates most commonly know.

Approach 3 — Bottom-Up Tabulation: Eliminate recursion entirely. Allocate an array dp of size n+1. Set dp[0] = 0, dp[1] = 1. Fill dp[i] = dp[i-1] + dp[i-2] for i from 2 to n. Return dp[n]. Time complexity: O(n). Space complexity: O(n) for the array. This approach eliminates call stack overhead, avoids potential stack overflow for large n, and is often faster in practice due to better cache locality. Understanding why bottom-up produces the same result as top-down is the key conceptual insight: both approaches compute the same subproblems in a DAG of dependencies; top-down discovers the order lazily, bottom-up imposes the order explicitly.

Approach 4 — Space-Optimized (O(1) Space): Observe that dp[i] depends only on dp[i-1] and dp[i-2]. You do not need the entire dp array — only the last two values. Replace the array with two variables: prev2 = F(n-2), prev1 = F(n-1). At each step, compute curr = prev1 + prev2, then shift: prev2 = prev1, prev1 = curr. Return prev1 after n-1 iterations. Time complexity: O(n). Space complexity: O(1). The space-optimized Fibonacci solution requires only two variables — this O(1) space, O(n) time approach is directly applicable to Climbing Stairs, House Robber, and Min Cost Climbing Stairs.

Bonus — Matrix Exponentiation: For truly large n (n > 10^6), even O(n) time becomes expensive. Matrix exponentiation reduces Fibonacci to O(log n) time by expressing the recurrence as a matrix multiplication and using fast exponentiation. The matrix [[1,1],[1,0]] raised to the nth power gives [[F(n+1), F(n)],[F(n), F(n-1)]]. This approach is rarely asked in standard interviews but appears as a follow-up in senior-level rounds or competitive programming contexts.

Dynamic programming is not a data structure or an algorithm — it is a problem-solving technique applicable when a problem has two specific properties: overlapping subproblems and optimal substructure. Understanding these properties in the context of Fibonacci is the clearest path to recognizing them in any problem.

Fibonacci Number (#509) is the minimal example of a DP problem because it has both required DP properties: overlapping subproblems and optimal substructure. Overlapping subproblems means the same subproblems are solved multiple times in the naive recursive approach. Computing F(10) requires F(9) and F(8). F(9) requires F(8) and F(7). F(8) is computed twice. F(7) is computed three times. F(6) is computed five times. The number of redundant computations grows exponentially — this is precisely what memoization addresses.

Optimal substructure means the optimal solution to the whole problem can be constructed from optimal solutions to subproblems. F(n) = F(n-1) + F(n-2) is the simplest DP recurrence — the solution for n is constructed exactly from solutions for n-1 and n-2. There is no ambiguity, no choice to make, no branching decision. In more complex DP problems — like Knapsack or Longest Common Subsequence — optimal substructure involves choosing among multiple subproblem combinations to find the maximum or minimum. Fibonacci strips away this complexity and shows the structure in isolation.

The recurrence relation F(n) = F(n-1) + F(n-2) is the algebraic statement of optimal substructure for the Fibonacci problem. In every DP problem, identifying the recurrence relation is the hardest and most important step. For Fibonacci, the recurrence is given by the problem definition. For Climbing Stairs, it must be derived: 'to reach step n, I came from step n-1 or step n-2 — so ways(n) = ways(n-1) + ways(n-2)'. This is the same recurrence. The pattern is identical. Only the problem framing differs.

Understanding Fibonacci as a DP problem rather than a math problem reframes every subsequent DP problem you encounter. When you see a problem with a recursive structure and redundant subcomputation, you now have a complete mental model: identify the subproblems, define the recurrence, choose top-down or bottom-up, and optimize space if only recent states are needed. This mental model, practiced on Fibonacci, applies without modification to dozens of LeetCode problems and to the DP questions in real technical interviews.

Once you internalize the Fibonacci recurrence — f(n) = f(n-1) + f(n-2) — you begin to see it everywhere. A surprising number of LeetCode problems, including several that appear in real technical interviews at top companies, reduce directly to this pattern. Recognizing the Fibonacci skeleton inside a differently-framed problem is a genuine interview skill that separates candidates who have internalized DP from those who have merely memorized solutions.

Climbing Stairs (#70) is the most direct Fibonacci variant. You can climb 1 or 2 steps at a time. How many distinct ways can you reach the nth step? The recurrence is ways(n) = ways(n-1) + ways(n-2): the number of ways to reach step n equals the number of ways to reach step n-1 (then take one step) plus the number of ways to reach step n-2 (then take two steps). This is exactly the Fibonacci recurrence with different base cases: ways(1) = 1, ways(2) = 2. The connection between climbing stairs and Fibonacci is so tight that the two problems share the same optimal implementation word-for-word.

Min Cost Climbing Stairs (#746) adds a cost array to Climbing Stairs. At each step i, you pay cost[i] to step off from that stair. The recurrence becomes minCost(n) = min(minCost(n-1) + cost[n-1], minCost(n-2) + cost[n-2]). The structure is still Fibonacci — only two preceding states matter — but the combination operation is min() instead of sum(). This is the first generalization of the Fibonacci pattern: the same state dependency, a different aggregation function.

House Robber (#198) is a Fibonacci variant with a forbidden-adjacency constraint. You cannot rob two adjacent houses. The recurrence is rob(n) = max(rob(n-1), rob(n-2) + nums[n]): either you skip house n and take the best from house n-1, or you rob house n and add it to the best from house n-2. Again, only two preceding states are needed. The space-optimized solution is identical in structure to the space-optimized Fibonacci: maintain two variables, update them at each step.

Decode Ways (#91) maps digit strings to letter decodings (1='A', 26='Z'). The recurrence is ways(i) = (valid 1-char decode) * ways(i-1) + (valid 2-char decode) * ways(i-2). The number of decodings at position i depends on the one or two characters ending at i and the number of ways to decode what came before. The Fibonacci recurrence structure is preserved; the base cases and validity checks add complexity but the dependency graph is identical.

Tribonacci Number (#1137) extends the recurrence to three preceding states: T(n) = T(n-1) + T(n-2) + T(n-3). The same four solution approaches apply. The space-optimized solution requires tracking three variables instead of two. Recognizing Tribonacci as a Fibonacci generalization — same recurrence structure, one additional term — makes it immediately solvable for anyone who has internalized the Fibonacci pattern.

Fibonacci is not just a warm-up problem — it is the first rung of a well-defined skill ladder that leads to the most complex DP problems on LeetCode. Each rung builds on the previous by adding one new complexity: a second dimension, a longer dependency window, a branching choice, or a structural constraint. Understanding where Fibonacci sits on this ladder — and what each subsequent rung requires — turns DP preparation from a chaotic exploration into a systematic progression.

Rung 1 — 1D Linear DP (Fibonacci, Climbing Stairs, House Robber): The state is a single index i, the recurrence depends on a fixed number of preceding states (1 or 2), and the space optimization is always possible by maintaining a sliding window of recent states. Every problem at this level shares the same implementation skeleton. Time O(n), Space O(1) optimized.

Rung 2 — 1D DP with Unbounded Lookback (Coin Change, Longest Increasing Subsequence, Word Break): The state is still a single index i, but the recurrence may depend on any preceding state — not just the last 1 or 2. Space optimization to O(1) is generally not possible because the dependency window is unbounded. These problems require O(n) space and O(n^2) time in the naive formulation, with optimizations available for specific problems (patience sorting for LIS reduces to O(n log n)).

Rung 3 — 2D DP (Unique Paths, Minimum Path Sum, Edit Distance, Longest Common Subsequence): The state is a pair (i, j) — two indices into two sequences, or a position in a grid. The recurrence expresses the optimal value at (i,j) in terms of values at (i-1,j), (i,j-1), and/or (i-1,j-1). Time O(m*n), Space O(m*n) or O(min(m,n)) with row-by-row optimization. Edit Distance and LCS are the canonical examples.

Rung 4 — Interval DP (Burst Balloons, Matrix Chain Multiplication, Palindrome Partitioning): The state is an interval [i,j], and the recurrence considers all split points k within [i,j]. Time O(n^3), Space O(n^2). These problems require recognizing that the optimal solution for an interval depends on optimal solutions for all sub-intervals — a significantly more abstract form of optimal substructure than Fibonacci's linear dependency.

Rung 5 — Tree DP and Graph DP (Binary Tree Maximum Path Sum, Unique BSTs, DP on DAGs): The state is a node in a tree or graph. The recurrence aggregates results from children or neighbors. These problems require combining DP with tree/graph traversal, and the 'base cases' are leaves or nodes with no outgoing edges. The Fibonacci recurrence applied to a tree would be: the value at a node is the sum of values at its children — which is exactly how post-order aggregation works.

The insight that makes this ladder navigable: every rung is a generalization of the one below it, not a separate concept. 2D DP is 1D DP applied twice. Interval DP is 1D DP where the 'index' is an interval. Tree DP is 1D DP where the 'sequence' is a path from root to leaf. If you have genuinely internalized Fibonacci — not just memorized it — every subsequent rung is a recognizable extension.

Despite being an Easy problem, Fibonacci surfaces a predictable set of mistakes in interview settings. These mistakes are not signs of low ability — they are signs of candidates who solved the problem mechanically without understanding it. An interviewer who asks Fibonacci as a warm-up is watching for exactly these mistakes, because how a candidate handles the easy version predicts how they will handle the hard versions.

Base case errors are the most common mistake. LeetCode's definition for #509 is F(0) = 0, F(1) = 1. Many candidates write F(0) = 1, F(1) = 1 (the mathematical convention used in some textbooks). This produces wrong answers for n=0 and n=1. Always confirm the base cases from the problem statement before writing any solution — a habit that becomes critical in complex DP problems where base case errors are much harder to diagnose.

Off-by-one errors in the iterative solution appear when candidates write for i in range(2, n) instead of range(2, n+1), returning dp[n-1] instead of dp[n]. These errors are caused by rushing to code before fully thinking through the indices. The correct pattern: initialize dp with n+1 elements, fill indices 2 through n inclusive, return dp[n].

n=0 and n=1 edge cases trip up the space-optimized solution when candidates try to run the loop without checking whether n is already a base case. The correct implementation: handle n==0 and n==1 as immediate returns before entering the loop. Without this guard, the loop body executes with uninitialized state for small inputs.

Failing to recognize Fibonacci variants in disguise is the highest-stakes mistake. If an interviewer presents Climbing Stairs or House Robber and you do not immediately recognize the Fibonacci recurrence structure, you are likely to spend 10-15 minutes deriving from scratch what should take 30 seconds to identify. The ability to say 'this is the Fibonacci recurrence — I can apply the same space-optimized approach' in the first minute of the problem is what distinguishes a candidate who has internalized DP from one who is pattern-searching.

Not offering the matrix exponentiation follow-up is a missed opportunity in senior-level interviews. If you implement the O(n) space-optimized solution cleanly, a strong interviewer may ask: 'Is there an even faster approach?' The correct answer is matrix exponentiation for O(log n) time. You do not need to implement it — explaining the approach and its complexity is sufficient. Mentioning this proactively (before being asked) demonstrates depth of knowledge beyond the standard preparation.

Fibonacci Number is the DP alphabet. Just as you cannot read without knowing letters, you cannot solve Hard DP problems without a deep understanding of the Fibonacci recurrence, why it qualifies as a DP problem, and how each optimization (memoization, tabulation, space reduction) changes the computational profile. Every minute spent truly understanding Fibonacci is leveraged across dozens of subsequent DP problems.

The four-approach progression — naive recursion, memoization, tabulation, space-optimized — is not just a solution catalog. It is a complete tutorial on the DP thought process. Recursion teaches you to express the problem in terms of subproblems. Memoization teaches you to eliminate redundant computation. Tabulation teaches you to work bottom-up and eliminate recursion overhead. Space optimization teaches you to identify the minimal state required. Each step is a lesson that applies directly to harder problems.

When you encounter Climbing Stairs, recognize the Fibonacci recurrence in thirty seconds and write the space-optimized solution in two minutes. When you encounter House Robber, recognize the Fibonacci recurrence with a max() aggregation and derive the solution in three minutes. When you encounter Edit Distance, recognize the 2D DP extension of the Fibonacci dependency structure and approach it with confidence. This recognition — fast, automatic, and grounded in deep understanding — is what strong DP performance in technical interviews looks like.

YeetCode spaced repetition is particularly effective for internalizing the Fibonacci recurrence pattern because the recurrence f(n) = f(n-1) + f(n-2) needs to become automatic — something you can write without thinking while your cognitive attention is focused on the harder aspects of a disguised variant. Spaced repetition of Fibonacci and its direct variants (Climbing Stairs, House Robber, Min Cost Climbing Stairs) over a two-week period creates the muscle memory that carries into the interview room.

Solve Fibonacci four ways. Implement each approach cleanly, from memory, in a fresh editor. Explain the complexity of each approach aloud. Then solve the six problems listed in Section 4, applying the same recurrence with different framing. Then move to Rung 2 of the skill ladder. This is the correct order of operations — and candidates who follow it consistently outperform those who jump directly to Hard problems.