Went after the LeetCode challenge Coin Change 2 which you can find at the following URL: https://leetcode.com/problems/coin-change-2/?tab=Description
There are two approaches typically used to solve this type of problem. They are:
| Recursion |
| Dynamic Programming |
I consider dynamic programming more of an art than a science. I believe developers need to use it often enough to solve adequate problems to achieve and maintain proficiency in the technique.
I visited the Wikipedia page on Dynamic Programming and took notes which I present in the following couple paragraphs. That is simpler and quicker than starting from scratch ;o)
Dynamic programming (also known as dynamic optimization) is a method for solving a complex problem by breaking it down into a collection of simpler subproblems, solving each of those subproblems just once, and storing their solutions – ideally, using a memory-based data structure.
The next time the same subproblem occurs, instead of recomputing its solution (typically encountered with recursion), one simply looks up the previously computed solution, thereby saving computation time at the expense of a modest expenditure in storage space. (Each of the subproblem solutions is indexed in some way, typically based on the values of its input parameters, so as to facilitate its lookup). The technique of storing solutions to subproblems instead of recomputing them is called “memoization”.
Dynamic programming algorithms are often used for optimization. A dynamic programming algorithm will examine the previously solved subproblems and will combine their solutions to give the best solution for the given problem. In comparison, a greedy algorithm treats the solution as some sequence of steps and picks the locally optimal choice at each step. Using a greedy algorithm does not guarantee an optimal solution, because picking locally optimal choices may result in a bad global solution, but it is often faster to calculate. Fortunately, some greedy algorithms are proven to lead to the optimal solution.
On a separate note, I have received “complaints” from readers that the code in this blog is not “optimally” formatted. That is correct. I just copy code from the IDE and paste it into WordPress. Will reveal the reason why I have been doing so towards the end of this year. That said; I will start formatting the code properly in this post. I want to thank GC for his suggestion to evaluate and use the WordPress plugin “Code Snippets”. That did not seem to be the best fit for what was needed. Instead decided to use the “SyntaxHighlighter Evolved” plugin.
Now let’s talk about the actual challenge. I first went with a recursive approach. It passed the three test cases as illustrated by the following screen console captures from the Eclipse IDE:
5 1 2 5 main <<< amount: 5 main <<< line ==>1 2 5<== main <<< coins: 1 2 5 main <<< recursive change: 4 duration: 0 ms 3 2 main <<< amount: 3 main <<< line ==>2<== main <<< coins: 2 main <<< recursive change: 0 duration: 0 ms 10 10 main <<< amount: 10 main <<< line ==>10<== main <<< coins: 10 main <<< recursive change: 1 duration: 0 ms
The Java code for this approach follows:
/**
* Entry point for recursion.
*/
static int changeRecursive (int amount, int[] coins) {
return changeRecursive(amount, coins, 0);
}
/**
* Recursive call.
*/
static int changeRecursive(int amount, int[] coins, int i) {
// **** this is a solution ****
if (amount == 0) {
return 1;
}
// **** this is NOT a solution ****
if (amount < 0) { return 0; } // **** NO solution available **** if ((amount > 0) && (i == coins.length)) {
return 0;
}
// **** next try ****
return changeRecursive(amount - coins[i], coins, i) + changeRecursive(amount, coins, i + 1);
}
The code ran some test cases but then encountered the following one and …
500 3 5 7 8 9 10 11 main <<< amount: 500 main <<< line ==>3 5 7 8 9 10 11<== main <<< coins: 3 5 7 8 9 10 11 main <<< recursive change: 35,502,874 duration: 27,227 ms
You probably guessed what happened. The test timed out :o(
This challenge is quite faster (more on that in a few) when solved using dynamic programming. Allow me to show the console screen capture for when comparing recursion against dynamic programming:
500 3 5 7 8 9 10 11 main <<< amount: 500 main <<< line ==>3 5 7 8 9 10 11<== main <<< coins: 3 5 7 8 9 10 11 main <<< recursive change: 35,502,874 duration: 27,227 ms main <<< dynamic programming change: 35,502,874 duration: 0 ms
Of course, recursion is a viable solution for some subset of conditions. In this case it is not.
Let me show you a screen capture that displays a two dimensional array used to store solutions for previous subproblems. In this case I use the data from the first test code example:
5 1 2 5 main <<< amount: 5 main <<< line ==>1 2 5<== main <<< coins: 1 2 5 main <<< recursive change: 4 duration: 0 ms displayMatrix <<< rows: 4 (coins + 1) cols: 6 (amount + 1) >--amount--> 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 displayMatrix <<< rows: 4 (coins + 1) cols: 6 (amount + 1) >--amount--> 1 0 0 0 0 0 1 1 1 1 1 1 1 1 2 2 3 3 1 1 2 2 3 4 main <<< dynamic programming change: 4 duration: 8 ms
Please disregard the duration for the dynamic programming case because it mostly reflects the delay to display the two dimensional array twice.
Following is the Java code for the solution including the method used to display the matrix:
/**
* Display matrix.
*/
static void displayMatrix(int[][] matrix, int rows, int cols) {
System.out.println("displayMatrix <<< rows: " + rows + " (coins + 1) cols: " + cols + " (amount + 1)"); System.out.println(" >--amount-->");
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
System.out.printf("%2d " , matrix[r]);
}
System.out.println();
}
}
/**
* Same requirements but now using dynamic programming.
*/
public static int change(int amount, int[] coins) {
// **** ****
int[][] matrix = new int[coins.length + 1][amount + 1];
// **** if amount == 0 then just return empty set to make the change ****
for (int row = 0; row <= coins.length; row++) {
matrix[row][0] = 1;
}
// **** if no coins given, 0 ways to change the amount ****
for (int col = 1; col <= amount; col++) {
matrix[0][col] = 0;
}
// **** display matrix (COMMENT OUT when timing operation) ****
displayMatrix(matrix, coins.length + 1, amount + 1);
// **** loop once per coin (per row) ****
for (int row = 1; row <= coins.length; row++) {
// **** loop once per amount (per column)****
for (int col = 1; col <= amount; col++) {
// **** check if coin value is less than or equal to the amount needed ****
if (coins[row - 1] <= col) {
// **** INCLUDE this coin ****
// [1] reduce amount by coin value and
// [2] use subproblem solution (amount - v[i]) and
// [3] add solution from top to it
// add solution from top reduce amount by coin value
// (prev row, same col) use subproblem solution
matrix[row][col] = matrix[row - 1][col] + matrix[row][col - coins[row - 1]];
} else {
// **** EXCLUDE this coin ****
// copy value from previous row in same column
matrix[row][col] = matrix[row - 1][col];
}
}
}
// **** display matrix (COMMENT OUT when timing operation) ****
displayMatrix(matrix, coins.length + 1, amount + 1);
// **** result in lower right corner ****
return matrix[coins.length][amount];
}
I tried describing in some depth the algorithm so I created the following illustration:
The code uses two loops. The outer loop traverses the coin values represented by the rows of the array. The inner loop traverses the columns of the array which represent the amount.
At the core of the inner loop there is an “if” statement. It decides to include (amount not exceeded) or exclude (amount exceeded) the current coin.
My test code follows:
/**
* Test code.
*/
public static void main(String[] args) {
int change;
long begin;
long end;
long duration;
// **** open scanner ****
Scanner sc = new Scanner(System.in);
// **** ****
int amount = sc.nextInt();
System.out.println("main <<< amount: " + amount);
sc.nextLine();
// **** coins ****
String line = sc.nextLine();
System.out.println("main <<< line ==>" + line + "<==");
String[] tmp = line.split(" ");
int[] coins = new int[tmp.length];
for (int i = 0; i < coins.length; i++) {
coins[i] = Integer.parseInt(tmp[i]);
}
// **** ****
System.out.print("main <<< coins: ");
for (int c : coins) {
System.out.print(c + " ");
}
System.out.println();
// **** close scanner ****
sc.close();
// **** recursive approach (17 of 27 test cases passed and then time out) ****
begin = System.currentTimeMillis();
change = changeRecursive(amount, coins);
end = System.currentTimeMillis();
duration = end - begin;
System.out.println("main <<< recursive change: " + change + " duration: " + duration + " ms");
// **** dynamic programming (27 test cases passed) ****
begin = System.currentTimeMillis();
change = change(amount, coins);
end = System.currentTimeMillis();
duration = end - begin;
System.out.println("main <<< dynamic programming change: " + change + " duration: " + duration + " ms");
}
In my humble opinion, once you become familiar with a solution it seems reasonable and easy. Coming up with it is not that simple and requires a considerable amount of time. In my case I got inspiration by reading several online articles on dynamic programming some of which included code which I adapted to this challenge. This makes me wonder if any software developer (without memorizing a solution before hand) would be able to produce code on a white board to solve this challenge.
If you have comments or questions regarding this or any other post in this blog please do not hesitate and send me a message. I will respond as soon as possible and will not use your name unless you explicitly allow me to do so.
John
john.canessa@gmail.com
Follow me on Twitter: @john_canessa