#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/dynamic-programming/dynamic-programming-fundamentals/fibonacci-o-1-space

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████████████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/dynamic-programming/dynamic-programming-fundamentals/fibonacci-o-1-space

Repovive

LeetCode 509 Fibonacci - O(1) Space - Dynamic Programming Fundamentals | Dynamic Programming | Repovive

Repovive.

Dynamic Programming21 sections · 918 units60h total

Open in Course

LeetCode 509 Fibonacci - O(1) Space

Most efficient

Here's the space-improved Fibonacci:

function fib(n)
    if n ≤ 1 then
        return n
    prev2 := 0
    prev1 := 1
    for i from 2 to n
        current := prev1 + prev2
        prev2 := prev1
        prev1 := current
    return prev1

Use two variables instead of an array. computes the next Fibonacci number and updates your "window." Time: $O(n)$ , space: $O(1)$ .

Let's see your process: You started with code that would run for years and used so much memory. Now you have code that runs in microseconds using two variables. Same problem and same answer, but completely different performance.

This is what DP gives you: the ability to see waste and eliminate it.