[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

n	1	2	3	4	5	6	7	8	9
fib(n)	1	1	2	3	5	8	13	21	24

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)

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

https://www.youtube.com/watch?v=oBt53YbR9Kk

Tags