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?

Enroll in our 5-day mini coding interview class

/* | |

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

} |