state 5 of 32 · 5 min

The cells the formula cannot fill

A recurrence describes how a cell depends on smaller ones. Some cells have nothing smaller, and those must be supplied.

Counting how many

Look at how far back the recurrence reaches.

code

f(n) = f(n-1) + 1              -> one base case
f(n) = f(n-1) + f(n-2)         -> two
f(n) = f(n-1) + f(n-3)         -> three, because n-3 needs 0, 1 and 2 present

For a two dimensional table it is usually the first row and the first column, and sometimes the cell where they meet needs its own value.

They carry the meaning

A base case is an answer, not an initial value, and it should be a sentence you can defend.

code

edit[i][0] = i    turning the first i characters into an empty string
                  takes i deletions
ways[0]    = 1    there is exactly one way to do nothing
best[0]    = 0    the best value from no items is zero

The counting one trips people. ways[0] = 1 looks wrong, since there are no steps to climb. But the empty solution is a solution, and setting it to zero makes every value in the table zero, because everything is built from it.

Zero is not neutral

Initialising a table to zero and hoping is the most common source of a wrong answer that never crashes.

Problem	Correct fill	Zero would mean
Maximum value	0, or negative infinity	"achievable with value 0"
Minimum cost	infinity for unreachable	"free", so everything routes through it
Counting	0, and 1 for the empty case	no ways at all
Reachability	false	not reachable

The minimum case is the dangerous one. A minimum over a table containing false zeroes picks them, so the answer comes out far too low and looks like a plausible number.

Unreachable is a value

For "exactly this sum" style problems, some states genuinely cannot happen, and they need a marker distinct from a legitimate answer.

python

NEG = float('-inf')
best = [NEG] * (target + 1)
best[0] = 0                     # only the empty selection is reachable

Using zero here would claim every amount is achievable with value zero, and the maximum would happily select one.

The habit

Write the base cases before the loop, say out loud what each one means, and set the loop to start exactly where they stop. Most off by one errors are really a base case that was assumed rather than stated.