Recurrence Relation for this dynamic programming algorithm G

Recurrence Relation for this dynamic programming algorithm

Given a set of distinct coins with these denominations, D = {15, 10, 5}, use a dynamic programming approach to determine the minimum number of coins needed to make up the amount 50. Be sure to include your recurrence relationship along with any initial conditions and your table.

Solution

The minimum number of coins required to make up a value V can be computed using following recursive formula.

If V == 0, then coins required is 0 to make up V.
If V > 0
% if V is greater than 0 then, minimum number of coins required to make up a value of V by the below recursive method
minCoin(coins[0..m-1], V) = min {1 + minCoins(V-coin[i])}
i=0 to n-1 and coin[i] <= V

Java Code:

class MinimumCoin

{

// s represents the size of coins array

static int minCoins(int coins[], int s, int V)

{

if (V == 0) return 0;
  

// Initialize result

int result = Integer.MAX_VALUE;

  
// use for loop to check every coin that has smaller value than V

for (int i=0; i<s; i++)

{

if (coins[i] <= V)

{

int sub_result = minCoins(coins, s, V-coins[i]);

  

// Check for INT_MAX to avoid overflow and see if

// result can minimized

if (sub_result != Integer.MAX_VALUE && sub_result + 1 < result)

result = sub_result + 1;

}

}

return result;

}

public static void main(String args[])

{

int coins[] = {15, 10, 5};

int s = coins.length;

int V = 50;

System.out.println(\"the Minimum coins required to make up the amount 50 \"+ minCoins(coins, s, V) );

}

}