DP base cases

A transition tells you how to build a state's answer from smaller states, but you cannot build forever — at some point you reach the smallest states, the ones with no smaller pieces to lean on. Those are the base cases, and you must fill in their answers directly, by hand, from the meaning of the problem. They are the foundation the whole table rests on. If the foundation is wrong, every value computed on top of it inherits the error, so base cases deserve as much care as the recurrence itself.

Concretely, base cases are the entries you write before any loop or recursion, the ones the transition is not allowed to compute. For Fibonacci they are fib(0)=0 and fib(1)=1. For the longest common subsequence, dp[i][0] = 0 and dp[0][j] = 0, meaning that the LCS of any string with the empty string is empty. For edit distance, dp[i][0] = i (turning a length-i string into the empty string costs i deletions) and dp[0][j] = j (j insertions). For a counting DP, the base case is often dp[empty] = 1 — there is exactly one way to do nothing. Each base case is a tiny instance whose answer you can read off without any recursion, and getting its value right (is it 0, 1, infinity, or i?) is a problem-specific judgement.

Base cases also encode the boundary of feasibility. In an optimization where infeasible situations must be ruled out, you often seed impossible states with a sentinel — positive infinity for a minimization, negative infinity for a maximization — so that the 'best' operation automatically avoids them. A classic example is coin change: dp[0] = 0 (zero coins make amount 0) while dp[amount] starts at infinity for every positive amount, so an amount that cannot be formed stays infinite and is never mistaken for achievable. Off-by-one and wrong-sentinel errors at the boundary are among the most common DP bugs, precisely because the rest of the table looks correct while quietly building on a bad edge.