 Dynamic programming recurrence

An equation expressing the optimum or count for a dynamic programming state in terms of smaller or otherwise previously computable states. A valid dependency order, base cases, and a proof that every candidate solution is represented are required. The minimum coin change recurrence follows by classifying a nonempty solution by its last coin.