Dynamic Programming

Let's avoid duplicate work

Dynamic Programming is a technique for solving problems with overlapping subproblems.

For example, Let's take calculating Fibonacci. Refer to the recursive algorithm below.

index: 1,2,3,4,5,6...
Fibonacci number: 1,1,2,3,5,8...

function Fib(n) {
    if (n < 3)
        return 1
    else
        return FibF(n-1) + Fib(n-2)
}

In divide and conquer, each step is repeated over and over again. See the below example. Let's run Fib(5)

Fib(5) = Fib(4) + Fib(3)
       = {Fib(3)+Fib(2)} + {Fib(2)+Fib(1)}
       = {[Fib(2)+Fib(1)]+1} + {1+1}
       = 1+1+1+1+1

In dynamic programming, Each step (sub-problem) is solved only once and the result of each step is stored(cache). This is called “memoization” in dynamic programming. This is also called the Top-down approach to solving the problems in dynamic programming. Using this, speed can be drastically improved. As cons, it takes space for the variable storage.

Sample pseudo code with Memoization

var dict = new Dictionary<int,int>();
for i=1 to n
    dict[i] = -1

function Fib(n) {
    if (n < 3)
        return 1
    else
    {
        if (dict[n] == -1)
            dict[n] = Fib(n-1) + Fib(n-2)

        return dict[n]                
    }
}

Now, there are problems where the top-down approach/memoization is the only feasible solution because the problem space is so big that it is not possible to solve all subproblems. However, the “caching” still works in a reasonable time because your input only needs a fraction of the subproblems to be solved. But it is too tricky to explicitly define, which subproblems you need to solve, and hence to write a bottom-up solution. On the other hand, there are situations when you know you will need to solve all subproblems. In this case, go on and use the bottom-up.

Sample pseudo code with the Bottom-Up approach

public int Bottom-Up(int n) {
    int[] fib = new int[n + 1];
    fib[1] = 1;
    fib[2] = 1;
    for (int i = 3; i <= n; i++) {
        fib[i] = fib[i - 1] + fib[i - 2];
    }
    return fib[n];
}

Now if we look into this algorithm it actually starts from lower values then goes to the top. If we need the 5th Fibonacci number, we start calculating 1st, then second then third all the way to up 5th number. So-called bottom-up approach.

In this example of Fibonacci, Both of these approaches have similar space and time complexity. You need to take a decision on the correct approach by considering Ease of coding, Recursiveness, Optimality, and Practical concerns.

Thanks !!

Happy Learning …