Quick Expense Manger. Your free expense manager. Lots of features. The application is also ad free.

Dynamic Programming and Misconception

Posted on Nov. 10, 2017
dynamic-programming

Whenever someone tells me that they have used dynamic programming approach in their algorithm, I see their pride filled glittering eyes. Dynamic programmings are indeed tricky and if you have successfully implemented one, you should be proud of yourself. But there are many confusions about dynamic programming. Some says it's just recursion with a hash-map. But actually it's more than that.

Let's consider the famous coin change problem. You have an infinite number of coins of some specific denominations say denominations 1, 2 and 3. And you have to find minimum number of coins that you can use to sum up to an amount say 10.

So, if you look at this problem, there are many ways to achieve that sum.


  1. 10 coins of denomination 1 to get the sum 10

  2. 5 coins of denomination 2 to get the sum 10

  3. 2 coins of denomination 3 and 2 coins of denomination 2 to get the sum 10

The answer is the point (3) which uses only 4 coins to get the sum where as (1) and (2) uses more than 4 coins.

Following is a recursive approach to achieve this solution.

import java.util.*;
class Solution{
public int findMinCoins(int amount,int [] denomArray,int coinsUsed){
if(amount==0)
return coinsUsed;
int min = Integer.MAX_VALUE;
for(int d : denomArray){
if(amount-d>=0)
min = Math.min(min,findMinCoins(amount-d,denomArray,coinsUsed));
}
min +=1;
return min;
}
public void run(){
int [] denomArray = {1,2,3};
int amount = 10;
System.out.println(findMinCoins(amount,denomArray,0));
}
public static void main(String [] args){
new Solution().run();
}
}

At each recursive step you just branch off with all the possible denominations which satisfies the condition amount-d>=0 and you end up duplicating many sub problems as shown below.


You have a sub problem of amount 8 under 10 and the same sub problem is under 9. Similarly you have the same sub problem 6 under 9, 8 and 7 and it continues like this until you reach the base case.

To avoid computing the same sub problem again and again we can have a Cache which is nothing but a Hash-map. So, before computing a sub problem, we first look at the cache to check if we have already computed that sub problem or not. If no - we go ahead and compute it. Otherwise we simply return the result of the computation which we have stored in the cache as shown below.

import java.util.*;
class Solution{
Map<Integer,Integer> cache;
public int findMinCoins(int amount,int [] denomArray,int coinsUsed){
if(cache.containsKey(amount))
return cache.get(amount);
if(amount==0){
return coinsUsed;
}
int min = Integer.MAX_VALUE;
for(int d : denomArray){
if(amount-d>=0)
min = Math.min(min,findMinCoins(amount-d,denomArray,coinsUsed));
}
min+=1;
cache.put(amount,min);
return min;
}
public void run(){
int [] denomArray = {1,2,3};
int amount = 10;
cache = new HashMap<Integer,Integer>();
System.out.println(findMinCoins(amount,denomArray,0));
}
public static void main(String [] args){
new Solution().run();
}
}

This approach is called memoization. Many people think this as dynamic programming. But it's not. You are still having the duplicates. You may not be computing them but still looking into the Cache multiple times for the same sub problem.

Dynamic programming is much more elegant than this. It's pure art. It's a bottom up approach. It starts with the base case. If you look at the recursion, you will notice that it's a top down approach. You are directly starting with the given amount and going down to smaller amounts. But with the dynamic programming approach we will start with the base denominations and will gradually climb up the ladder until we reach the final amount. Watch this.

import java.util.*;
class Solution{
public void run(){
int [] denomArray = {1,2,3};
int amount = 10;
int [] result = new int[amount+1];
result[1] = result[2] = result[3] = 1;
for(int i = 4; i<=amount; i++){
result[i] = Integer.MAX_VALUE;
for(int d : denomArray){
result[i] = Math.min(result[i],1+result[i-d]);
}
}
System.out.println(result[amount]);
}
public static void main(String [] args){
new Solution().run();
}
}

This is pure beauty. But the thing is - you have to compute all the sub problems once even though they may not contribute to the final problem. You can notice the same in the result array that we have declared. It has a slot for each and every sub-problem. So, if the input amount is very high, you may run out of memory.

It's very difficult to see the pattern until and unless you practice as many dynamic programs as possible. But before trying your hands in dynamic programming, first become very very comfortable with recursion and memoization and see what are you storing in the cache.

Top Coder has a good collection of dynamic programming questions. You can try those.

Please leave your queries in the comments section.

Sharing is Caring!

Quick Expense Manger. Your free expense manager. Lots of features. The application is also ad free.

GET FREE UPDATES


profile image

Kaushik Baruah


ABOUT

My name is Kaushik Baruah and I am the chief blogger on this Blog. I have developed this Blog from scratch using Django as the backend and here I like to share my experience as software engineer and research engineer with my online readers. I will try to focus on career planning, latest emerging technologies and tutorials on various computer science subjects. You can follow me on Twitter, Facebook and Google+

GET FREE UPDATES

POPULAR POSTS

Copyright © 2018
About Us

My name is Kaushik Baruah and I am the chief blogger on this Blog. I have developed this Blog from scratch using Django as the backend and here I like to share my experience as software engineer and research engineer with my online readers. I will try to focus on career planning, latest emerging technologies and tutorials on various computer science subjects.

Get Free Updates