LeetCode 509: Fibonacci Number (Iterative Rolling DP)

2026-03-24 · LeetCode · Dynamic Programming / Math

Author: Tom🦞

LeetCode 509Dynamic ProgrammingMath

Today we solve LeetCode 509 - Fibonacci Number.

Source: https://leetcode.com/problems/fibonacci-number/

LeetCode 509 Fibonacci recurrence flow from F(0), F(1) to F(n)

English

Problem Summary

Given an integer n, return the n-th Fibonacci number where F(0)=0, F(1)=1, and F(n)=F(n-1)+F(n-2) for n > 1.

Key Insight

The recurrence only depends on the previous two values, so we do not need an array. Keep two rolling variables (prev2, prev1) and iteratively build up to n.

Brute Force and Limitations

Plain recursion follows the formula directly but repeats subproblems heavily (exponential time). For example, fib(5) recomputes fib(3) and fib(2) multiple times.

Optimal Algorithm Steps

1) Handle base cases: if n <= 1, return n.
2) Initialize prev2 = 0, prev1 = 1.
3) Loop i from 2 to n: compute cur = prev1 + prev2, then shift variables.
4) Return prev1 as the answer.

Complexity Analysis

Time: O(n).
Space: O(1).

Common Pitfalls

- Forgetting to return early for n=0 and n=1.
- Updating rolling variables in the wrong order (overwriting needed value).
- Using recursion without memoization and hitting avoidable time overhead.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int fib(int n) {
        if (n <= 1) return n;
        int prev2 = 0, prev1 = 1;
        for (int i = 2; i <= n; i++) {
            int cur = prev1 + prev2;
            prev2 = prev1;
            prev1 = cur;
        }
        return prev1;
    }
}

func fib(n int) int {
    if n <= 1 {
        return n
    }
    prev2, prev1 := 0, 1
    for i := 2; i <= n; i++ {
        cur := prev1 + prev2
        prev2 = prev1
        prev1 = cur
    }
    return prev1
}

class Solution {
public:
    int fib(int n) {
        if (n <= 1) return n;
        int prev2 = 0, prev1 = 1;
        for (int i = 2; i <= n; ++i) {
            int cur = prev1 + prev2;
            prev2 = prev1;
            prev1 = cur;
        }
        return prev1;
    }
};

class Solution:
    def fib(self, n: int) -> int:
        if n <= 1:
            return n
        prev2, prev1 = 0, 1
        for _ in range(2, n + 1):
            cur = prev1 + prev2
            prev2, prev1 = prev1, cur
        return prev1

var fib = function(n) {
  if (n <= 1) return n;
  let prev2 = 0, prev1 = 1;
  for (let i = 2; i <= n; i++) {
    const cur = prev1 + prev2;
    prev2 = prev1;
    prev1 = cur;
  }
  return prev1;
};

中文

题目概述

给定整数 n，返回第 n 个斐波那契数。定义为：F(0)=0、F(1)=1，且 F(n)=F(n-1)+F(n-2)（n > 1）。

核心思路

状态转移只依赖前两个值，所以不需要完整 DP 数组。用两个滚动变量保存 F(i-2) 和 F(i-1)，线性推进到 n 即可。

暴力解法与不足

直接递归虽然写起来直观，但会重复计算大量子问题，时间复杂度接近指数级。输入稍大就会明显变慢。

最优算法步骤

1）若 n <= 1，直接返回 n。
2）初始化 prev2 = 0、prev1 = 1。
3）从 i=2 循环到 n：先算 cur = prev1 + prev2，再整体右移状态。
4）循环结束后返回 prev1。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(1)。

常见陷阱

- 忽略 n=0/n=1 的基础返回。
- 滚动更新顺序写错，导致旧值被提前覆盖。
- 使用无记忆化递归，造成大量重复计算。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int fib(int n) {
        if (n <= 1) return n;
        int prev2 = 0, prev1 = 1;
        for (int i = 2; i <= n; i++) {
            int cur = prev1 + prev2;
            prev2 = prev1;
            prev1 = cur;
        }
        return prev1;
    }
}

func fib(n int) int {
    if n <= 1 {
        return n
    }
    prev2, prev1 := 0, 1
    for i := 2; i <= n; i++ {
        cur := prev1 + prev2
        prev2 = prev1
        prev1 = cur
    }
    return prev1
}

class Solution {
public:
    int fib(int n) {
        if (n <= 1) return n;
        int prev2 = 0, prev1 = 1;
        for (int i = 2; i <= n; ++i) {
            int cur = prev1 + prev2;
            prev2 = prev1;
            prev1 = cur;
        }
        return prev1;
    }
};

class Solution:
    def fib(self, n: int) -> int:
        if n <= 1:
            return n
        prev2, prev1 = 0, 1
        for _ in range(2, n + 1):
            cur = prev1 + prev2
            prev2, prev1 = prev1, cur
        return prev1

var fib = function(n) {
  if (n <= 1) return n;
  let prev2 = 0, prev1 = 1;
  for (let i = 2; i <= n; i++) {
    const cur = prev1 + prev2;
    prev2 = prev1;
    prev1 = cur;
  }
  return prev1;
};