Brendan Ang

Search

Search IconIcon to open search

Making Change

Last updated Nov 8, 2022 Edit Source

# Making Change

# Problem Formulation

Note that The minimum number of coins to form value x, is 1 + the minimum of the solutions to value $x-d_1, x-d_2….x-d_k$

We can form the following recurrence equations: Base case (when n-d less than 0): $$change(n)=0, \forall i\in{1,…,m},n-d_i < 0$$ Finding the minimum of subproblems: $$change(n)=\min_{i=1…m,d_i\le n}(1+change(n-d_i))$$

# Strategy

# Pseudocode

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

int coinchange (int n) {
	int change[n+1]; // initialize dp array
	for (int j=0; j<=n; j++) {
		
		change[j] = MAXINT // MAXINT is the maximum integer value
		
		for(int i=0;i<m;i++){
			if(j-val[i]>=0) {
				change[j] = min(change[j],change[j-val[i]]+1)
			}
		}
		
		if(change[j]== MAXINT) {
			change[j]=0; // If no changes means base case 0
		}
	}
	return change[n]
}

Backlinks

Interactive Graph