Algorithm - Dynamic Programming (DP)

DP is an algorithm design techniques that involves finding a solution to problems using “controlled brute force” problem solving in polynomial time. In this article we will explore Memoization.

Example : Fibonacci - exponential time

F(n)=F(n1)+F(n2)F(n) = F(n-1) + F(n-2)

Fibonacci algorithm implementation with a exponential running time.

1
2
3
4
5
6
7
8
9
10
11
12
const fibonacci = (n) => { // 1, 1, 2, 3, 5, 8, 13...
if (n <= 2)
return 1;

return fibonacci(n - 1) + fibonacci(n - 2);
};
(() => {
console.log(fibonacci(2)); // 1
console.log(fibonacci(3)); // 2
console.log(fibonacci(6)); // 8
console.log(fibonacci(11)); // ... 89
})();

The exponential work come from having to repeatedly calculating the sub-problem for each sequence in F(n). Below depicts a tree representing the work needed to calculate the F(n-1) and F(n-2) Fibonacci sequence.

Exponential time implementation of Fibonacci algorithm.

We can see that solutions for a sub-problem can be reused. The algorithm can be improved by reusing the solutions calculated from a sub-problem, technique known as Memoization.

Time complexity (exponential time)

Below shows the time complexity for exponential time Fibonacci algorithm. We first look at the cost of the sub-problem. In Fibonacci, the sub-problem is repeated for each sequence (F1, F2, …, Fn).

T(n)=T(n1)+T(n2)+θ(1)T(n) = T(n-1) + T(n-2) + \theta(1)

The upper bound for time complexity can be expressed as:

T(n)=T(n2)+T(n2)+θ(1)T(n) = T(n-2) + T(n-2) + \theta(1) or T(n)=2T(n2)+θ(1)T(n) = 2T(n-2) + \theta(1)

So the time complexity for all the sub-problems for F(n):

T(n)2(n/2)T(n) \ge 2 ^ {(n/2)} ... or ... θ(2n)\large \theta (2 ^ n)

Memoization

Memoization caches the results for a sub-problem so that work is not repeated. For an exponential amount of work, Memoization can significantly improve algorithm performance. Below is an example of using Memoization to improve the Fibonacci algorithm.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const fibonacciMemoized = () => {
const memoized = [];
const fibonacci = (n) => {
if (n <= 2) return 1;
// Once memoized subsequence F(n) does not need to recalculate "(Fn) tree".
if (memoized[n]) return memoized[n];
memoized[n] = fibonacci(n - 1) + fibonacci(n - 2);
return memoized[n];
};
return { fibonacci }
};
(() => { // 1, 1, 2, 3, 5, 8, 13...
const fm = fibonacciMemoized();
console.log(fm.fibonacci(6)); // 8
console.log(fm.fibonacci(11)); // ... 89
})();

Bottom-up

Bottom-up approach is the same as Dynamic Programming with Memoization. The only difference is that Bottom-up approach does not use recursion (no call stack tree). In the example of finding nth Fibonacci, Bottom-up builds the values towards nth sequence.

Another way of looking at Bottom-up approach is a Topological sort from F1 to Fn.

Exponential time implementation of Fibonacci algorithm.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
const fibonacciBottomUp = (n) => {
if (n <= 2) return 1;
let fib1 = 1;
let fib2 = 1;
let tmp;
for (let x = 2; x < n; x++) {
tmp = fib1 + fib2;
fib1 = fib2; // Memoization
fib2 = tmp;
}
return fib2;
};
(() => { // 1, 1, 2, 3, 5, 8, 13...
console.log(fibonacciBottomUp(3)); // 8
console.log(fibonacciBottomUp(6)); // 8
console.log(fibonacciBottomUp(11)); // ... 89
})();

Time complexity (Memoization / Bottom-up)

The time complexity is the sum of all the sub-problems. Asymptotically We can treat the sub-problem work as constant time:

T(n)=n(T(work sub-problem))T(n) = n (T(\text{work sub-problem}))

Note that Memoized calls are constant time, so the complexity is dependent on the number of non-memoized operations needed to calculate F(n). This means the complexity is linear time … θ(n)\theta(n)