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

💡 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