Introduction to Dynamic Programming

Joshua Kyalo's photo
Joshua Kyalo
·

6 min read

Table of contents

Introduction

Dynamic Programming is an optimization algorithm for recursive functions.

The Problem

The problem with recursive solutions is that in some cases, the repeated recursive calls may be used to compute a problem already computed before, but whose value has not been stored and so must be recomputed. This is a misuse of the processor's time and the process would be made significantly faster if we had a cache to store the results of the computations in order to avoid redundant function calls.

To demonstrate the power of dynamic programming, we will look at a typical recursive problem; the Fibonacci sequence. This is a series of numbers ie 0,1,1,2,3,5,8,13...

The value of a number in the series is the sum of the two preceeding values. Mathematically, we can express this relationship as shown below;

Fn = Fn-1 + Fn-2

Recursive Solution

The problem can be solved recursively; the function will repeatedly call itself. All our code will be inside the function fib. The function will take an Integer argument, which will represent the nth Fibonacci number.

function fib (n){

    }

As per the equation to find the nth Fibonacci number, the 5th Fibonacci Number is the sum of the 4th Fibonacci Number and the 3rd. This means that the function call must be repeated with lesser values for n until a base case is reached.

A base case is a case whose value will always be known. In this case, the 0th value is 0 and the 1st is 1.

function fib (n){
    if (n < 2){
        return n;
    }
}

After this, the recursive part of the problem is explored.

function fib (n){
    if (n < 2){
        return n;
    }
    else{
        return fib (n-1) + fib (n-2);  
        }
}

Inefficiency of Recursive Method

Suppose n = 5

The return statement will compute until the base case. Its result will be;

fib (4) + fib (3)

When fib (4) is called, it will compute;

fib (3) + fib (2)

fib (3) is been computed a second time, and to compute fib (3), we would compute fib(2) again which is also repeated.

When the value of n increases, the number of such repeated function calls increases. This means that a lot of computational time would be saved if we stored the value of each function call so that a function calls are not repeated needlessly. This is called memoization.

Another issue with the recursive call is that for large values of n, we could get a stack overflow error.

Solution Using Recursive With Memoization

Memoization is the storage of the result of a computation so that it can be subsequently retrieved without repeating the computation. The technique is mainly used for optimization. It is a top down approach, meaning we compute from the highest value of n and move to the base cases.

In our example in the previous section, the result for the Fibonacci of 3 (which is equal to 2), is computed twice. We must have a way to store not only the value of the result (2), but also the input that produces that result; n = 3. Many data structures can be used to achieve this. For the simplicity of our code, arrays will be used.

Arrays store sequential data which can be accessed using indices. The index can be used to represent n, and the value stored at that particular index will be the result of Fib (n).

We will still be using a recursive approach to the problem. Before our function call, in the main block of our code, we must create our memo array.

The memo array is set to the size of n since it will store all the values until the nth value. Initially, all the values will be set to a default value; -1 in this case since Fibonacci numbers aren't negative. In this way, the program will be able to check whether a value has been stored on a particular index or not, and proceed to pick the stored value or store a new value respectively.

memo = new Array (n);
memo.fill(-1);

Later on, the fib function is called and its value stored in a variable for logging on the console.

memo = new Array (n);
memo.fill(-1);
let result = fib (n, memo);
console.log(memo);

This time, the fib function takes two parameters; memo, our array, and n.

Fib Function

Unlike in the purely recursive method, our function has 3 conditions to check for;

  1. The function must check if the value at n is -1.

  2. The function must check for the base cases and assign values accordingly.

  3. The function must compute the value of fib(n) if the value has not been computed before.

function fib (n,memo){
        if (memo[n] >= 0){
            return memo[n];
        }
        else if (n < 2){
            memo [n] = n;
            return n;
        }    
        else{
            memo [n] = fib (n-1, memo) + fib (n-2, memo);
            return memo [n];
        }
}

If the memo[n] is greater than or equal to 0, it would mean that the value at that index has already been computed once and it's value stored in place of the default value specified (-1). In this case the value will simply be returned.

This makes it so the program can compute much larger input than before and in a faster way.

Solution Using The Iterative Approach

In the iterative approach, we use loops instead of recursive functions. It is also called a bottom up approach since it starts at the base case and moves upwards towards the highest values of n

In this instance, the value of the 0th and 1st values of the memo array is set manually to 0 and 1 respectively. This gives us what would be the base case in recursive solutions.

let n = 70;
memo = new Array (n);
memo[0] = 0;
memo[1] = 1;

Once our base cases are set, it's time to begin the loop. The loop will have a counter that will run from i at 2 to i at n. This is because we start by computing the value that comes after the base cases (2) and move upwards. Here, there are no function calls and instead the memo array will be fully used to generate the next numbers in the sequence.

let n = 70;
memo = new Array (n);
memo[0] = 0;
memo[1] = 1;
for (i = 2; i <= n; i++){
        memo [i] = memo[i - 1] + memo[i - 2];
        result = memo [i];
}

However, the memo array is not ideal to use. This is because at any point of the program's running, only two values are used in the memo array after which they are not used again. We can avoid this use of memory by foregoing the use of an array at all.

What we can do instead is have two variabes; a and b, which will store the values that we need to calculate fib(n).

let n = 70;
a = 0;
b = 1;
for (i = 2; i <= n; i++){
    c = a + b;
    a = b;
    b = c;
}

c holds the value for the next number in the sequence, while a and b hold the value for the previous two numbers in the sequence. After each loop, a; first value, is equated to b; second value. In essence, the first value becomes the second value, then the third and so on and so forth.

General ProgrammingDynamic ProgrammingJavaScript