Minimum Coin Change Problem Recursive and DP Based solution

Minimum coin change problem tries to find minimum coins required to make a particular amount from a set of coins. A coin can be selected multiple times.



Example - C = {1, 2, 4, 5} i.e. We have coin value 1, 2, 4 and 5

and we want minimum number of coins required to make SUM =12

possible solutions for making a sum of 12  = {5, 5, 2} , {4, 4, 4}, {5, 4, 2 ,1} etc

so we need what can be minimum number of coin  so it will be 3.

Recursive Solution -

#include<stdio.h>
#define COIN_NUM 100
int coins[COIN_NUM];
int total_coin;
int getMinCoin(int);
int recur;
void main() {
    int i, required_amount, min_coin;
    scanf("%d", &total_coin);
    for (i=1;i<=total_coin;i++) {
        scanf("%d", &coins[i]);
    }
    scanf("%d", &required_amount);
        min_coin = getMinCoin(required_amount);
    printf("minimum required coin %d\n", min_coin);
    printf("%d iteration made", recur);
}

int getMinCoin(int amount) {
    int i;
    ++recur;
    if (amount == 0) {
        return 0;
    } else if (amount < 0) {
        return COIN_NUM;
    }
    int min = COIN_NUM;
    int minIndex = 0;
    for (i=1;i<=total_coin;i++) {
        int temp = getMinCoin(amount - coins[i]) + 1;
        if (temp < min) {
            min = temp;
            minIndex = i;
        }
    }
    return min;
}

So it take a lot of iteration to do this in recursive way. Complexity is 0(n^c)

We can use dynamic programming for reducing time complexity.

DP Based Solution -

#include<stdio.h>
#define MAX 32767;
int arr[1000];
int min(int a,int b)
{
    return (a>b)?b:a;
}
int coin_denomination_minm(int amount,int coin_array_length)
{
    if(amount==0)
        return 0;
    else if(amount<0)
        return MAX;
    if(coin_array_length==0)
        return MAX;
    return (min(coin_denomination_minm(amount-arr[coin_array_length-1],

coin_array_length)+1,coin_denomination_minm(amount,coin_array_length-1)));
}
void main()
{
    int v,n,i,total,minm_ways;
    printf("Enter the value\n");
    scanf("%d",&v);
    printf("Enter the total coins\n");
    scanf("%d",&n);
    for(i=0;i<n;i++)
            scanf("%d",&arr[i]);
    minm_ways=coin_denomination_minm(v,n);
    printf("The minimum ways are %d",minm_ways);
}