Published on

[Dynamic Programming] Fibonacci Sequence

Problem

Write a function fib(n) that takes in a number as an argument. The function should return the n-th number of the Fibonacci sequence

The 1st and 2nd number of the sequence is 1. To generate the next number of the sequence, we sum the previous two

n123456789
fib(n)112358132124

Brute Force Method


/**
 * This is the raw implementation of fib
 *  we have base cases
 *  we reduce the problem to sub-problem & following the definition
 *
 * @param n nth fib key
 * @returns {number|*}  the value
 */
const fibRaw = n => {
	if (n <= 2) return 1;

	return fibRaw(n - 1) + fibRaw(n - 2)
}

Call Stack for FibRaw(7)

Call Stack for FibRaw(7)

Complexity Analysis FibRaw

Foo O(n) Bar O(n) Dib O(2^n) Dib O(n) Lib O(n) Fib O(2^n)

Memoization

const fibMemo = (n, memo = {}) => {
	if(n in memo) return memo[n]
	if(n <= 2) return 1

	memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo)
	return memo[n]
}

Call Stack for FibMemo(6)

Call Stack for FibMemo(7)

Complexity Analysis FibMemo

FibMemo O(n)

FibTab

const fibTab = (n) => {
	const table = Array(n + 1).fill(0)
	table[1] = 1;

	// each fib number contributes to next 2
	for(let i = 0; i <= n; i++) {
		table[i + 1] += table[i]
		table[i + 2] += table[i]
	}
	return table[n]
}

fibTab

Complexity

  • Time O(n)
  • Space O(n)

Reference