Skip to content
Work Practice Products Coding interviews Machine learning coding Quant developer HFT course Blog Method Why me About Enquire Book a call

Coding · Dynamic programming

Base cases

Lesson · 8 min read · Dynamic programming · Base cases

Where the recurrence stops, the answer must be written in by hand. Some base cases come from the problem; others exist only so the recurrence works.

Where they come from

Follow the recurrence downwards from any state and it eventually reaches a state it cannot reduce further. Those are the base cases, and they come in two kinds:

  • Genuine: the problem itself answers them. Zero coins pay amount 0. An empty string has edit distance equal to the length of the other string. One way to stand still.
  • Boundary: states the recurrence points at although the problem has no such situation, such as a negative amount or a position before the start. Their value is chosen so that they never win: the identity of the combine operator.
optboundary valuewhy
min+∞an impossible option can never be the smallest
max−∞it can never be the largest
sum (counting)0it contributes no ways
or (feasibility)falseit never makes something possible

A worked example

Fewest coins to pay a, coins 3 and 5. The recurrence best(a) = 1 + min(best(a − 3), best(a − 5)) has the genuine base case best(0) = 0. It also reaches negative amounts, and amounts like 1, 2, 4 and 7 that cannot be paid at all. Giving negative amounts the value ∞ makes the recurrence handle every case with no special code: an unpayable amount simply ends up at ∞.

Coins 3 and 5. Negative amounts are boundary states worth ∞.

  1. Step 1 / 12
    best
    00·1·2·3·4·5·6·7·8·9·10·11

    Base case: best[0] = 0.

  2. Step 2 / 12
    best
    00∞1·2·3·4·5·6·7·8·9·10·11

    best(1) = 1 + min(best(-2) = ∞, best(-4) = ∞) = ∞.

  3. Step 3 / 12
    best
    00∞1∞2·3·4·5·6·7·8·9·10·11

    best(2) = 1 + min(best(-1) = ∞, best(-3) = ∞) = ∞.

  4. Step 4 / 12
    best
    00∞1∞213·4·5·6·7·8·9·10·11

    best(3) = 1 + min(best(0) = 0, best(-2) = ∞) = 1.

  5. Step 5 / 12
    best
    00∞1∞213∞4·5·6·7·8·9·10·11

    best(4) = 1 + min(best(1) = ∞, best(-1) = ∞) = ∞.

  6. Step 6 / 12
    best
    00∞1∞213∞415·6·7·8·9·10·11

    best(5) = 1 + min(best(2) = ∞, best(0) = 0) = 1.

  7. Step 7 / 12
    best
    00∞1∞213∞41526·7·8·9·10·11

    best(6) = 1 + min(best(3) = 1, best(1) = ∞) = 2.

  8. Step 8 / 12
    best
    00∞1∞213∞41526∞7·8·9·10·11

    best(7) = 1 + min(best(4) = ∞, best(2) = ∞) = ∞.

  9. Step 9 / 12
    best
    00∞1∞213∞41526∞728·9·10·11

    best(8) = 1 + min(best(5) = 1, best(3) = 1) = 2.

  10. Step 10 / 12
    best
    00∞1∞213∞41526∞72839·10·11

    best(9) = 1 + min(best(6) = 2, best(4) = ∞) = 3.

  11. Step 11 / 12
    best
    00∞1∞213∞41526∞72839210·11

    best(10) = 1 + min(best(7) = ∞, best(5) = 1) = 2.

  12. Step 12 / 12
    best
    00∞1∞213∞41526∞72839210311

    best(11) = 1 + min(best(8) = 2, best(6) = 2) = 3. Amounts 1, 2, 4 and 7 stay at ∞: they cannot be paid. Report them as −1 at the end, not inside the table.

Padding the table

Two-sequence problems (common subsequences, edit distance) index states by prefix lengths 0 to n, not by positions 0 to n − 1. The extra row and column hold the empty-prefix base cases, and every cell of the real problem then has the neighbours its recurrence reads. Off-by-one errors in DP almost always come from mixing "length i" and "index i"; choose one, write it next to the table, and stick to it.

In Python, use float("inf") rather than a large number for ∞, or check for it before adding: ∞ + 1 is still ∞, but a sentinel like 10⁹ can overflow in other languages and quietly beat a real answer after enough additions.