keetcoder

# 509. Fibonacci Number

LeetCode Problem Link (opens new window)

The Fibonacci numbers, commonly denoted F(n), form a sequence called the Fibonacci sequence. The sequence starts with 0 and 1, and each subsequent number is the sum of the two preceding ones. That is: F(0) = 0, F(1) = 1 F(n) = F(n - 1) + F(n - 2), where n > 1 Given n, calculate F(n).

Example 1:

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

Example 2:

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

Example 3:

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

Constraints:

  • 0 <= n <= 30

# Thought Process

The Fibonacci sequence should be very familiar to most. It's a great introductory problem for practicing dynamic programming.

Because this problem is quite simple, some might not even need any analysis and can just write the solution directly.

However, the style of "Code Thought Record" is: Simple problems are meant to deepen the understanding of solving methodologies.

This problem allows you to initially see how the dynamic programming five-step process is used to solve problems.

Without a methodology, you might be able to immediately solve simple problems, but a slightly more complicated one leaves you at a loss.

So the dynamic programming five-step process I summarize is to be used throughout the entire dynamic programming series, just like the Recursive Three-Step Process for Binary Trees (opens new window) and the Backtracking Three-Step Process for Backtracking Algorithm (opens new window). Over time, you will realize how important the dynamic programming five-step process is.

# Dynamic Programming

Dynamic programming five-step process:

Here, we need a one-dimensional dp array to save the results of the recursion.

  1. Determine the dp array and the meaning of the indices

The definition of dp[i] is: The Fibonacci number at position i is dp[i].

  1. Determine the recurrence relation

Why is this problem considered a simple introductory question?

Because the problem gives us the recurrence relation directly: The state transition equation dp[i] = dp[i - 1] + dp[i - 2];

  1. How to initialize the dp array

The problem also directly tells us how to initialize it:

dp[0] = 0;
dp[1] = 1;
1
2
  1. Determine the order of traversal

From the recursion formula dp[i] = dp[i - 1] + dp[i - 2]; we can see that dp[i] relies on dp[i - 1] and dp[i - 2], so the order of traversal must be from front to back.

  1. Example to derive the dp array

According to this recurrence relation dp[i] = dp[i - 1] + dp[i - 2], when N is 10, the dp array should be as follows:

0 1 1 2 3 5 8 13 21 34 55

If the code doesn't produce the correct result, print out the dp array to see if it matches the derived sequence.

Having analyzed the problem using dynamic programming, here is the C++ code:

class Solution {
public:
    int fib(int N) {
        if (N <= 1) return N;
        vector<int> dp(N + 1);
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= N; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[N];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
  • Time Complexity: O(n)
  • Space Complexity: O(n)

You may notice that we only need to maintain two numbers without recording the entire sequence.

Here's the code:

class Solution {
public:
    int fib(int N) {
        if (N <= 1) return N;
        int dp[2];
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= N; i++) {
            int sum = dp[0] + dp[1];
            dp[0] = dp[1];
            dp[1] = sum;
        }
        return dp[1];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
  • Time Complexity: O(n)
  • Space Complexity: O(1)

# Recursive Solution

This problem can also be solved using a recursive solution.

Here's the code:

class Solution {
public:
    int fib(int N) {
        if (N < 2) return N;
        return fib(N - 1) + fib(N - 2);
    }
};
1
2
3
4
5
6
7
  • Time Complexity: O(2^n)
  • Space Complexity: O(n), considering the stack space used by the system for recursion

The time complexity for this recursive approach can be understood by drawing a tree diagram. If it's unclear, please refer to this article: Explain Time Complexity of Recursive Algorithms with an Interview Problem! (opens new window)

# Summary

The Fibonacci sequence is a fundamental problem in dynamic programming and will be mentioned multiple times throughout the discussion of this topic!

In this explanation, I strictly followed the dynamic programming five-step process outlined in the Dynamic Programming Fundamentals (opens new window). Some might find these analysis steps unnecessarily complicated and might code directly right away.

However, let me emphasize again: Simple problems are used to master methodologies. The dynamic programming five-step process will be important in discussions of dynamic programming problems that follow, so stay tuned!

That’s it, learn algorithms step by step with "Code Thought Record"!

# Other Language Versions

# Java

class Solution {
    public int fib(int n) {
        if (n < 2) return n;
        int a = 0, b = 1, c = 0;
        for (int i = 1; i < n; i++) {
            c = a + b;
            a = b;
            b = c;
        }
        return c;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
// Non-compressed state version
class Solution {
    public int fib(int n) {
        if (n <= 1) return n;             
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        for (int index = 2; index <= n; index++){
            dp[index] = dp[index - 1] + dp[index - 2];
        }
        return dp[n];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

# Python

Dynamic Programming (Version 1)


class Solution:
    def fib(self, n: int) -> int:
       
        # Exclude Corner Case
        if n == 0:
            return 0
        
        # Create dp table 
        dp = [0] * (n + 1)

        # Initialize dp array
        dp[0] = 0
        dp[1] = 1

        # Traversal order: From front to back. Since later states rely on earlier ones
        for i in range(2, n + 1):

            # Determine the recursive/relation formula
            dp[i] = dp[i - 1] + dp[i - 2]
        
        # Return the answer
        return dp[n]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

Dynamic Programming (Version 2)


class Solution:
    def fib(self, n: int) -> int:
        if n <= 1:
            return n
        
        dp = [0, 1]
        
        for i in range(2, n + 1):
            total = dp[0] + dp[1]
            dp[0] = dp[1]
            dp[1] = total
        
        return dp[1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

Dynamic Programming (Version 3)

class Solution:
    def fib(self, n: int) -> int:
        if n <= 1:
            return n
        
        prev1, prev2 = 0, 1
        
        for _ in range(2, n + 1):
            curr = prev1 + prev2
            prev1, prev2 = prev2, curr
        
        return prev2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

Recursion (Version 1)


class Solution:
    def fib(self, n: int) -> int:
        if n < 2:
            return n
        return self.fib(n - 1) + self.fib(n - 2)
1
2
3
4
5
6

# Go

func fib(n int) int {
    if n < 2 {
        return n
    }
    a, b, c := 0, 1, 0
    for i := 1; i < n; i++ {
        c = a + b
        a, b = b, c
    }
        return c
}
1
2
3
4
5
6
7
8
9
10
11

# JavaScript

Solution 1

var fib = function(n) {
    let dp = [0, 1]
    for(let i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2]
    }
    console.log(dp)
    return dp[n]
};
1
2
3
4
5
6
7
8

Solution 2: Time Complexity O(N), Space Complexity O(1)

var fib = function(n) {
    // In the state transition process of dynamic programming, the current result only depends on the results of the previous two elements, so two variables can replace the dp array to record the state process, reducing space complexity to O(1).
    let pre1 = 1
    let pre2 = 0
    let temp
    if (n === 0) return 0
    if (n === 1) return 1
    for(let i = 2; i <= n; i++) {
        temp = pre1
        pre1 = pre1 + pre2
        pre2 = temp
    }
    return pre1
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

# TypeScript

function fib(n: number): number {
    /**
        dp[i]: Fibonacci number at index i
        dp[0]: 0;
        dp[1]: 1;
        ...
        dp[i] = dp[i - 1] + dp[i - 2];
     */
    const dp: number[] = [];
    dp[0] = 0;
    dp[1] = 1;
    for (let i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# C

Dynamic Programming:

int fib(int n){
    // When n <= 1, return n
    if(n <= 1)
        return n;
    // Dynamically allocate an int array of size n+1
    int *dp = (int *)malloc(sizeof(int) * (n + 1));
    // Set the 0th index to 0, 1st index to 1
    dp[0] = 0;
    dp[1] = 1;

    // Traverse the array from front to back (i=2; i <= n; ++i), the element at index n is dp[i-1] + dp[i-2]
    int i;
    for(i = 2; i <= n; ++i) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

Recursive Approach:

int fib(int n){
    // If n is less than or equal to 1, return n
    if(n <= 1)
        return n;
    // Otherwise, return fib(n-1) + fib(n-2)
    return fib(n-1) + fib(n-2);
}
1
2
3
4
5
6
7

# Rust

Dynamic Programming:

impl Solution {
    pub fn fib(n: i32) -> i32 {
        if n <= 1 {
            return n;
        }
        let n = n as usize;
        let mut dp = vec![0; n + 1];
        dp[1] = 1;
        for i in 2..=n {
            dp[i] = dp[i - 2] + dp[i - 1];
        }
        dp[n]
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

Recursive Approach:

impl Solution {
    pub fn fib(n: i32) -> i32 {
        if n <= 1 {
            n
        } else {
            Self::fib(n - 1) + Self::fib(n - 2)
        }
    }
}
1
2
3
4
5
6
7
8
9

# Scala

Dynamic Programming:

object Solution {
  def fib(n: Int): Int = {
    if (n <= 1) return n
    var dp = new Array[Int](n + 1)
    dp(1) = 1
    for (i <- 2 to n) {
      dp(i) = dp(i - 1) + dp(i - 2)
    }
    dp(n)
  }
}
1
2
3
4
5
6
7
8
9
10
11

Recursion:

object Solution {
  def fib(n: Int): Int = {
    if (n <= 1) return n
    fib(n - 1) + fib(n - 2)
  }
}
1
2
3
4
5
6

# C#

Dynamic Programming:

public class Solution
{
    public int Fib(int n)
    {
        if(n<2) return n;
        int[] dp = new int[2] { 0, 1 };
        for (int i = 2; i <= n; i++)
        {
            int temp = dp[0] + dp[1];
            dp[0] = dp[1];
            dp[1] = temp;
        }
        return dp[1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

Recursion:

public class Solution
{
    public int Fib(int n)
    {
        if(n<2)
            return n;
        return Fib(n-1)+Fib(n-2);
    }
}
1
2
3
4
5
6
7
8
9
Last updated:: 9/4/2025, 3:19:38 PM

← 3. Climbing Stairs →

Copyright © 2025 keetcoder