Longest Common Subsequence

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?

Table of Contents
Enroll in our 5-day mini coding interview class

Code Sample

/*
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];
}
view raw ChoinChange2.java hosted with ❤ by GitHub