Fibonacci Number

LeetCode 1013 | Difficulty: Easy

Easy

Problem Description

The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), for n > 1.

Given n, calculate F(n).

Example 1:

Input: n = 2
Output: 1
Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.

Example 2:

Input: n = 3
Output: 2
Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.

Example 3:

Input: n = 4
Output: 3
Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3.

Constraints:

- `0 <= n <= 30`

Topics: Math, Dynamic Programming, Recursion, Memoization

---

Approach

Dynamic Programming

Break the problem into overlapping subproblems. Define a state (what information do you need?), a recurrence (how does state[i] depend on smaller states?), and a base case. Consider both top-down (memoization) and bottom-up (tabulation) approaches.

When to use

Optimal substructure + overlapping subproblems (counting ways, min/max cost, feasibility).

Mathematical

Look for mathematical patterns or formulas. Consider: modular arithmetic, GCD/LCM, prime factorization, combinatorics, or geometric properties.

When to use

Problems with clear mathematical structure, counting, number properties.

---

Solutions

Solution 1: C# (Best: 36 ms)

Metric	Value
Runtime	36 ms
Memory	14 MB
Date	2019-12-15

Solution

public class Solution {
    public int Fib(int N) {
         if(N < 2)
            return N;
        int[] memo = new int[N+1];
        memo[0] = 0;
        memo[1] = 1;
        for(int i=2; i<=N; i++)
            memo[i] = memo[i-1] + memo[i-2];
        return memo[N];
    }
}

📜 1 more C# submission(s)

Submission (2019-02-24) — 36 ms, 12.8 MB

public class Solution {
    public int Fib(int N) {
         if(N < 2)
            return N;
        int[] memo = new int[N+1];
        memo[0] = 0;
        memo[1] = 1;
        for(int i=2; i<=N; i++)
            memo[i] = memo[i-1] + memo[i-2];
        return memo[N];
    }
}

---

Complexity Analysis

Approach	Time	Space
Dynamic Programming	$O(n)$	$O(n)$

---

Interview Tips

Key Points

• Start by clarifying edge cases: empty input, single element, all duplicates.
• Define the DP state clearly. Ask: "What is the minimum information I need to make a decision at each step?"
• Consider if you can reduce space by only keeping the last row/few values.