How to solve Dynamic Programming(DP) problem?

Most common type of questions asked in interviews is on dynamic programming. DP is not the toughest topic to understand if your basic of programmings are strong.

Prerequisites for this topic is mentioned below

1. Basic Problem Solving
2. Recursion

If you are not able to figure out when to use recursion then I will highly recommend to go through recursion topic first before going ahead.

Definition —

Dynamic Programming (DP) is an algorithmic technique for solving an optimization problem by breaking it down into simpler sub-problems and utilizing the fact that the optimal solution to the overall problem depends upon the optimal solution to its sub problems

In simple terms, it is a technique to solve the problem by breaking into sub problems & memorize the sub-problem results so that it can be re-used.

How to approach such problems?

Lets take one example to explain-

Problem : Given number n find the nth term in Fibonacci series

To find out nth term, we need to just sum the n-1 term and n-2 term in Fibonacci series.

F(n) = F(n-1)+ F(n-2);

So we have divided our problem into sub problems & we will use results of sub-problem to get the overall result.

Code —

public int caculateFibonacci(int n){

if(n ≤ 2) return 1;

return caculateFibonacci(n-1) + caculateFibonacci(n-2);

}

We have successfully done with first part which was breaking into sub problems. Now, if you have noticed that there are some repeated recursive calls are executed.

Recursion Tree — No one reads the caption : )

As you can see in recursion tree, there are same repetitive calls (eg — calculateFibonacci(3))are made while executing the code. To optimize it, we will store the sub problem result & next time if code executes the same sub problem then we will return the result instead of executing the logic again.

We will use an array to store the sub problem results. Initially we will make all the values of array to -1 which indicates that particular sub problem is not evaluated till now & once we evaluate the result then we will store it in array.

int dp[] = new int[n];

Code —

public int caculateFibonacci(int n, int dp[]){

if(n ≤ 2) return 1;

if(dp[n] != -1) return dp[n];

dp[n] = caculateFibonacci(n-1) + caculateFibonacci(n-2);

return dp[n];

}

Conclusion -

1. Break down problem into sub problem
2. Find overlapping sub-problems(same repetitive recursive calls) & optimize it by storing into some data structure.

Follow for more articles similar to this & checkout other articles which are posted already. Comment for any suggestions.Like if you find it helpful.