Breaking
Dynamic programming

# Coin Change

Coin Change is the problem of finding the number of ways of making changes for a particular amount of cents, n, using a given set of denominations d{1} dots d{m}.

## source Code

```package com.dsacode.Algorithm.dynamic;

import java.util.Arrays;

public class CoinChange {
public static int[] minChange(int[] denom, int changeAmount)
{
int n = denom.length;
int[] count = new int[changeAmount + 1];
int[] from = new int[changeAmount + 1];

count = 1;
for (int i = 0 ; i < changeAmount; i++)
if (count[i] > 0)
for (int j = 0; j < n; j++)
{
int p = i + denom[j];
if (p <= changeAmount)
{
if (count[p] == 0 || count[p] > count[i] + 1)
{
count[p] = count[i] + 1;
from[p] = j;
}
}
}

if (count[changeAmount] == 0)
return null;

int[] result = new int[count[changeAmount] - 1];
int k = changeAmount;
while (k > 0)
{
result[count[k] - 2] = denom[from[k]];
k = k - denom[from[k]];
}

return result;
}
public static void main(String[] args) {
int [] arr=minChange(new int[]{1, 2, 5}, 10);
System.out.println("General coin change that keeps track of coins: "+Arrays.toString(arr));

}

}```

## Output

```General coin change that keeps track of coins: [5, 5]
```