DP: Given a value C we need to make amount of money C using unlimited supply of coins denominations of values V1,V2,V3,........Vn

Here we have an unlimited supply of coins of some given denominations,say

Coins[] = {V1,V2,V3,........Vn}

We have a amount C
We need to make a sum C using minimum number of coins possible.

This problem is similar to the Integer knapsack problem where we need to fill a knapsack of space S.
We need to optimally fill a knapsack of space S.

Here we need to optimally find the number of coins for an amount of money C using denominations V1,V2, -----, VN

Let M[j]  be the minimum number of coins required to make an amount of j

Then we can say

M[j] = min {M[j - Vi} + 1
            over all i

We can have the solution utilizing the recursive formula

int getMinCoins(int coins_val[], int total_coins, int value) {

    int minCoins[] = new int[value + 1];

    int coins = 65536;

    minCoins[0] = 0;

    for(int i = 1;i<=value;i++) {

        coins = 65536;

        for (int j=0;j<total_coins;j++){

            if (coins_val[j] <= i){

                coins = min(coins, minCoins[i-coins_val[j]]);

            }

        }

        

         if(coins< 65536) {

             minCoins[i] = coins + 1;

         } else {

             minCoins[i] = 65536;

         }

    }

    coins = minCoins[value];

    return coins;

}