delph

Posted on

# what is Dynamic Programming?

Dynamic programming is a way of making your algorithm more efficient by storing some of the intermediate results. It works well when your algorithms has a lot of repetitive computations.

In Dynamic Programming there are typically three steps you can take:

1. Come up with a recursive solution to the problem
2. Store or memoize the intermediate results if there are a lot of repeated computations
3. Come up with a bottom-up approach

## Recursive solution for fibonacci sequence

If we want to write a function `fib(n)` to find the nth number of a Fibonacci sequence.

Given the following Fibbonacci sequence: 1, 1, 2, 3, 5, 8, 13, 21, 34, ... `fib(3)` should return 2 and `fib(6)` should return 8.

A recursive solution to the problem without memoization:

``````function fib(n) {
if (n === 1 || n === 2) return 1;
return fib(n - 1) + fib(n - 2);
}
``````

The above solution works, but it is very inefficient.

From the diagram above, it can be seen that in order to calculate the 5th fibonacci number, `fib(5)`, we need to first compute `fib(4)` and `fib(3)` and add them up. In order to compute `fib(4)`, we then need to compute `fib(3)` again and `fib(2)`.

Hence it can be seen that there are a number of repeated computations, where we need to compute the return value for `fib(2)` three times, and `fib(3)` two times.

This becomes an issue when the value of `n` increases (eg. `fib(1000)`) and the time to calculate the `nth` Fibonacci grows exponentially, with a time complexity of O(2^n).

With Dynamic programming, we can store (ie. memoize) the return value of say, `fib(3)` after it is computed, and then use that value when it is needed again.

We can tweak the solution as follows:

1. Use an array with a length of `n + 1` , where the initial values are all set to null

2. Store the return value for `fib(n)` at index `n` of the array. (ie. 1, which is the return value of `fib(1)`, will be stored at `array[1]`)

3. At the beginning of the function, check whether the `array[n]` is `null` or not. If it is not `null`, it means that we have already stored the return value at index n, so we can just return `array[n]`. If it is not null, then we need to find the sum of the previous two Fibonacci numbers. and then store that result in `array[n]`

Rewriting the solution using memoization:

``````function fibWithMemoization(n) {
const memo = new Array(n + 1).fill(null);

function fib(n) {
if (memo[n] !== null) {
return memo[n];
}
if (n <= 2) {
return 1;
} else {
result = fib(n - 1) + fib(n - 2);
memo[n] = result;
return result;
}
}

return fib(n);
}
``````

This reduces the time complexity to O(n), however there is also a space complexity of O(n)

Also, as `n` increases, there is a possibility of a recursion error, which happens when there are too many calls on a call stack. To fix that, a bottom-up approach can be used.

## Bottom-up approach

In the bottom-up approach, we start from the smallest sub-problem and work our way up. In this case, we iterate up to `n` and store the earlier results in a table/ array.

``````function fib(n) {
if (n === 1 || n === 2) return 1;
arr[1] = 1;
arr[2] = 1;
for (let i = 3; i <= n; i++) {
arr[i] = arr[i - 1] + arr[i - 2];
}
return arr[n];
}
``````

With the bottom-up approach, the time complexity is O(n) and space complexity is constant.