Fibonacci Number

How it works

Each Fibonacci number depends only on the previous two numbers. Keep a fixed-size state and update it from lower indices upward so the old values are available when computing the new sum. This avoids exponential recursive recomputation.

Steps

1. Handle n = 0 and n = 1 directly.
2. Start from the values zero and one.
3. Iteratively sum the previous two values through n.

Complexity

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

Things to watch for

• Use F(0) = 0 and F(1) = 1.
• Preserve both old values before overwriting them.
• A full n-element DP array is unnecessary.

class Solution:
  def fib(self, n: int) -> int:
    if n < 2:
      return n

    dp = [0, 0, 1]

    for i in range(2, n + 1):
      dp[0] = dp[1]
      dp[1] = dp[2]
      dp[2] = dp[0] + dp[1]

    return dp[2]

class Solution {
 public:
  int fib(int n) {
    if (n < 2)
      return n;

    vector<int> dp{0, 0, 1};

    for (int i = 2; i <= n; ++i) {
      dp[0] = dp[1];
      dp[1] = dp[2];
      dp[2] = dp[0] + dp[1];
    }

    return dp.back();
  }
};