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

} |