Given a value V, if we want to make change for V cents, and we have infinite supply of each of C = { C1, C2, .. , Cm} valued coins, what is the minimum number of coins to make the change?
Examples:
Input: coins[] = {25, 10, 5}, V = 30
Output: Minimum 2 coins required
We can use one coin of 25 cents and one of 5 cents
Input: coins[] = {9, 6, 5, 1}, V = 11
Output: Minimum 2 coins required
We can use one coin of 6 cents and 1 coin of 5 cents
// "static void main" must be defined in a public class.
public class Main {
public static void main(String[] args) {
int[] coins = {1,3,5};
System.out.println(new Solution().minCoinChangeRecursiveWithMemo(coins, 3, 50));
System.out.println(new Solution().minCoinChangeDP(coins, 3, 50));
}
}
class Solution {
public int minCoinChangeRecursiveWithMemo(int[] coins, int m, int v){
HashMap<Integer, Integer> map = new HashMap<>();
return helper(coins, m, v, map);
}
public int helper(int[] coins, int m, int v, HashMap<Integer, Integer> map){
if(v == 0){
return 0;
}
if(map.containsKey(v)){
return map.get(v);
}
int min = Integer.MAX_VALUE;
for(int i = 0; i < m; i++){
if(coins[i] <= v){
int sub_res = helper(coins, m, v-coins[i], map);
if(sub_res != Integer.MAX_VALUE && sub_res + 1 < min){
min = sub_res+1;
}
}
}
map.put(v, min);
return min;
}
public int minCoinChangeDP (int[] coins, int m, int v){
int[] dp = new int[v+1];
dp[0] = 0;
for(int i= 1; i <= v; i++){
dp[i] = Integer.MAX_VALUE;
for(int j = 0; j < m; j++){
if(coins[j] <= i){
if(dp[i - coins[j]] + 1 < dp[i]) {
dp[i] = dp[i - coins[j]] + 1;
}
}
}
}
return dp[v];
}
}