0509. Fibonacci Number

Easy | DP | 12 ms (96.11%), 13.3 MB (90.24%)

❓ Problem Statement

Source: LeetCode - Fibonacci Number GitHub: Solution / Performance

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).

✍🏻 Constraints & Example

Constraints:

• 0 <= n <= 30

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

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

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

💡 Ideas

Instead of creating a 2D DP table, we could just rely on two variables since this simple DP question doesn't require too much past information.

It is quite straightforward that two variables store information of F(n-1) and F(n-2) respectively. And the initialized values are 0 and 1 respectively.

$$F(n) = F(n-1) + F(n-2), and\ F(0) = 0, F(1) = 1$$

🤖 Python3

class Solution:
    def fib(self, n: int) -> int:
        # (base case)
        if n == 0 or n == 1: return n
        
        # ==================================================
        #  Dynamic Programming                             =
        # ==================================================
        # time  : O(n)
        # space : O(1)

        n1, n2 = 0, 1
        for i in range(n - 1):
            n1, n2 = n2, n1 + n2
            
        return n2

🤖 Java

class Solution {
    /**
     * @time  : O(n)
     * @space : O(1)
     */

    public int fib(int n) {
        /* base case */
        if(n == 0 || n == 1) return n;
        
        int first = 0, second = 1;
        
        for(int i=0 ; i<n-1 ; i++) {
            int tmp = first;
            first = second;
            second += tmp;
        }
        
        return second;
    }
}