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]; | |
| } |