Skip to content

Instantly share code, notes, and snippets.

@ahmedengu
Created April 26, 2016 20:19
Show Gist options
  • Save ahmedengu/55ff6e7010abf341f9001d9ea48cb33a to your computer and use it in GitHub Desktop.
Save ahmedengu/55ff6e7010abf341f9001d9ea48cb33a to your computer and use it in GitHub Desktop.
Consider a country having monetary coins of values (2,3,7). a. Using dynamic programming, write an algorithm that finds the number of ways to construct an amount N. b. What is the complexity of your algorithm? c. Show the dynamic programming table for an input of N=10. For N=10 the solution is 3: (2,2,2,2,2) (2,2,3,3) (3,7).
public class CoinOfValues {
public static void main(String[] args) {
int number = 10;
int[] coins = {2, 3, 7};
int[][] dpMatrix = new int[coins.length + 1][number + 1];
for (int i = 0; i <= coins.length; i++)
dpMatrix[i][0] = 1;
for (int i = 1; i <= number; i++)
dpMatrix[0][i] = 0;
for (int i = 1; i <= coins.length; i++)
for (int j = 1; j <= number; j++)
if (coins[i - 1] <= j)
dpMatrix[i][j] = dpMatrix[i - 1][j] + dpMatrix[i][j - coins[i - 1]];
else
dpMatrix[i][j] = dpMatrix[i - 1][j];
for (int i = 0; i <= coins.length; i++)
for (int j = 0; j <= number; j++)
System.out.print(((j==0)?"\n":" ")+dpMatrix[i][j] );
System.out.println("\nresult: "+dpMatrix[coins.length][number]);
}
}
1 0 0 0 0 0 0 0 0 0 0
1 0 1 0 1 0 1 0 1 0 1
1 0 1 1 1 1 2 1 2 2 2
1 0 1 1 1 1 2 2 2 3 3
result: 3
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment