# Coin

Given a value N, this N means we need to make change for N cents, and we have infinite supply of each of S = { S1, S2, .. , Sm} valued coins, how many ways can we make the change?

## Solution

ways(i, j) = ways(i-s(j), j) + ways(i, j-1); i~[0,N], j~[1,m]

## Code

``````stepstr = input()
steps = stepstr.split()
test = int(input())

table = [[0 for x in range(len(steps))] for x in range(int(1E5+1))]
# Fill the enteries for 0 value case (n = 0)
for i in range(len(steps)):
table[0][i] = 1

last = 1
for t in range(0,test):
target = int(input())

# Fill rest of the table enteries in bottom up manner
for i in range(last, target+1):
for j in range(len(steps)):
# Count of solutions including S[j]
x = table[i - int(steps[j])][j] if i-int(steps[j]) >= 0 else 0

# Count of solutions excluding S[j]
y = table[i][j-1] if j >= 1 else 0

# total count
table[i][j] = x + y
table[i][j] %= 1E9+7;
if (target > last):
last = target
print(int(table[target][len(steps)-1]))

``````
``````int minNum(int[] S, int n) {
int[] dp = new int[n+1];
for (int i = 0; i < n+1; i++){
dp[i] = Integer.MAX_INT;
}
dp[0] = 0;
for (int i = 1; i <= n; i++){
for (int j = 0; j < m; j++){
if (i >= s[j] && dp[i] > dp[i-s[j]]){
dp[i] = dp[i-s[j]] + 1;
}
}
}
return dp[n];
}
``````

# Coin

Given an infinite number of quarters(25 cents), dimes(10 cents), nickels(5 cents), and pennies(1 cent), write code to calculate the number of ways of representing n cents.

## Solution

``````// Use the solution from the book to help understanding
public static int makeChange(int amount, int[] cents, int index){
if (index == cents.length - 1)
return 1;
int coin = cents[index];
int ways = 0;
for (int i = 0; i * coin <= amount; i++){
int rest = amount - i * coin;
ways += makeChange(rest, cents, index+1);
}
return ways;
}

public static int makeChange(int n){
int[] cents = {25, 10, 5, 1};
return makeChange(n, cents, 0);
}
``````