Sequence DP

Opening scenario

Problem references use LC for LeetCode.

Given an integer array nums, return the length of the longest strictly increasing subsequence (LC 300, Longest Increasing Subsequence). The interviewer then asks the same kind of question twice more. Coin change: given coin values and a target amount, return the fewest coins that add up to it, or -1 if none do. You may reuse the coin values without limit. Longest common subsequence: given two strings, return the length of the longest character sequence that appears in both, in order. These all share one skeleton. Finding it is the point.

A subsequence may skip elements but preserves their order. A subarray or substring must be contiguous. For coin change, denominations are positive and amount is non-negative. Begin by asking what a smaller solution must remember before you can append the next element.