We talk about the longest common subsequence in a..sequence. How do we think about this problem and how does dynamic programming decompose the subproblems to reach an optimal solution?
/* | |
Coin Change 2 - LeetCode: https://leetcode.com/problems/coin-change-2/ | |
All credit for code goes to user @tankztc: | |
https://leetcode.com/problems/coin-change-2/discuss/99212/Knapsack-problem-Java-solution-with-thinking-process-O(nm)-Time-and-O(m)-Space | |
This code passes all Leetcode test cases as of Jan. 11 2019 | |
Runtime: 13ms | |
Note: This code shows the use of O(mn) space. This problem can be solved using | |
only O(m) space. See the links above. | |
The video to explain this code is here: https://www.youtube.com/watch?v=DJ4a7cmjZY0 | |
*/ | |
public int change(int amount, int[] coins) { | |
/* | |
Each row represents using the denominations up to that point in | |
the denominations array (see the video explanation) | |
*/ | |
int[][] dp = new int[coins.length+1][amount+1]; | |
/* | |
Max ways to make change for 0 will be 1, doing nothing. | |
*/ | |
dp[0][0] = 1; | |
for (int i = 1; i <= coins.length; i++) { | |
/* | |
Set the subproblem for the amount of 0 to 1 when | |
solving this row | |
*/ | |
dp[i][0] = 1; | |
for (int j = 1; j <= amount; j++) { | |
int currentCoinValue = coins[i-1]; | |
/* | |
dp[i][j] will be the sum of the ways to make change not considering | |
this coin (dp[i-1][j]) and the ways to make change considering this | |
coin (dp[i][j] - currentCoinValue] ONLY if currentCoinValue <= j, otherwise | |
this coin can not contribute to the total # of ways to make change at this | |
sub problem target amount) | |
*/ | |
int withoutThisCoin = dp[i-1][j]; | |
int withThisCoin = currentCoinValue <= j ? dp[i][j - currentCoinValue] : 0; | |
dp[i][j] = withoutThisCoin + withThisCoin; | |
} | |
} | |
/* | |
The answer considering ALL coins for the FULL amount is what | |
we want to return as the answer | |
*/ | |
return dp[coins.length][amount]; | |
} |