Dynamic programming recurrence
= 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.