In DP solution for a problem is constructed from few or all previously found sub-solutions. DP solutions usually have a polynomial time complexity and such questions are basically asked during almost all programming interviews.
I will show you how to solve the famous Coinage DP Problem in this article.
Problem Description:
Given N coins of values val[0],val[1]...val[N-1] and a sum S. Find the minumum number of coins which can form Sum S. You can use same denominations more than once.
This can be solved in polynomial time if we can use polynomial space using dynamic programming. DP is all about relating solution to its subsolutions. Here, assume Sum(x) is what we want (Minimum number of coins which will add to x). Then Sum(x+1) can be found from all values Sum(1) to Sum(x) by the following definition :
for all i from 0 to N-1
Sum(x+1) = Min(Sum(x+1-val[i])+1)
The full java code is given Below :
import java.util.Arrays;
public class Coinage {
public Coinage() {
}
public static int Sum(int x,int val[]){
int[] dp = new int[x+1];
Arrays.fill(dp,99);
dp[0]=0;
for(int i=1 ;i < = x ;i++){
for(int j=0; j < val.length ;j++){
if(val[j] < = i && dp[i-val[j]]+1 < dp[i]){
dp[i]=dp[i-val[j]]+1;
}
}
System.out.println(Arrays.toString(dp));
}
return dp[x];
}
public static void main(String[] args) {
Coinage coinage = new Coinage();
int v[] = new int[]{1,3,5};
int ret = coinage.Sum(18,v);
System.out.println(ret);
}
}
OUTPUT:
[0, 1, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99]
[0, 1, 2, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99]
[0, 1, 2, 1, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99]
[0, 1, 2, 1, 2, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99]
[0, 1, 2, 1, 2, 1, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99]
[0, 1, 2, 1, 2, 1, 2, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99]
[0, 1, 2, 1, 2, 1, 2, 3, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99]
[0, 1, 2, 1, 2, 1, 2, 3, 2, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99]
[0, 1, 2, 1, 2, 1, 2, 3, 2, 3, 99, 99, 99, 99, 99, 99, 99, 99, 99]
[0, 1, 2, 1, 2, 1, 2, 3, 2, 3, 2, 99, 99, 99, 99, 99, 99, 99, 99]
[0, 1, 2, 1, 2, 1, 2, 3, 2, 3, 2, 3, 99, 99, 99, 99, 99, 99, 99]
[0, 1, 2, 1, 2, 1, 2, 3, 2, 3, 2, 3, 4, 99, 99, 99, 99, 99, 99]
[0, 1, 2, 1, 2, 1, 2, 3, 2, 3, 2, 3, 4, 3, 99, 99, 99, 99, 99]
[0, 1, 2, 1, 2, 1, 2, 3, 2, 3, 2, 3, 4, 3, 4, 99, 99, 99, 99]
[0, 1, 2, 1, 2, 1, 2, 3, 2, 3, 2, 3, 4, 3, 4, 3, 99, 99, 99]
[0, 1, 2, 1, 2, 1, 2, 3, 2, 3, 2, 3, 4, 3, 4, 3, 4, 99, 99]
[0, 1, 2, 1, 2, 1, 2, 3, 2, 3, 2, 3, 4, 3, 4, 3, 4, 5, 99]
[0, 1, 2, 1, 2, 1, 2, 3, 2, 3, 2, 3, 4, 3, 4, 3, 4, 5, 4]
4
RSS
