What should dp[0] hold in a bottom-up DP table indexed by items considered so far?

## The base case is a definition, not a formality Every bottom-up DP has three parts that must agree: what a cell *means*, how a cell is *computed* from earlier cells, and what the cells that no transition can compute must be *seeded* with. Beginners treat the third part as boilerplate ("fill the table with zeros and start the loop"), which is why so many first drafts are off by one. Start with the meaning. The most common convention over a sequence of `n` items is: > `dp[i]` = the answer for the **first `i` items**, i.e. for the prefix of length `i`. Under that convention `dp[0]` is not "item zero" and not "the first item" — it is the answer for the **empty prefix**. The table has `n + 1` cells, indices `0..n`, and the final answer is `dp[n]`. Item `k` (1-based) is folded in when computing `dp[k]`, so inside the loop the item at position `i` and the cell `dp[i]` line up with no adjustment. ## Seeding the empty prefix: use the identity of the combining operation Ask what the transition does to a value, and seed `dp[0]` with the value that leaves that operation unchanged: | What the DP computes | Transition combines with | `dp[0]` | |---|---|---| | Maximum or total accumulated value | addition | `0` | | Number of ways / arrangements | addition of counts, multiplication of independent choices | `1` (there is exactly one way to do nothing) | | Minimum cost, where some states are impossible | `min` | a sentinel larger than any real cost | | Reachability ("can this total be formed?") | logical `or` | reachable = true for the empty selection | The counting case trips people up: "there are zero items, so there are zero ways" sounds right and is wrong. There is exactly **one** way to build nothing — take nothing — and if you seed `0`, every count downstream multiplies or adds from zero and the whole table collapses to zero. The minimisation case is the mirror image: seeding an *unreachable* cell with `0` makes it look like a free, perfect solution, and the `min` happily propagates that fiction to the answer. ## Why the uniform transition matters A seeded `dp[0]` buys you a loop with no special cases: ``` dp[0] = identity for i in 1..n dp[i] = combine(dp[i-1], item i) answer = dp[n] ``` If instead you seed `dp[0]` with the first item's value, then `dp[1]` must not read `dp[0]` the way every other cell reads its predecessor, so you add a branch for `i == 1`. That branch duplicates the transition logic. When the recurrence later changes — a new term, a new constraint — you must remember to change it in two places, and the second place is the one that gets forgotten. ## Other index conventions, and what they do to the base case The prefix convention is not the only one, and each convention implies its own base case and its own final answer: - **`dp[i]` = the best answer for a solution that *ends exactly at* item `i`.** Now there is no meaningful empty state; you seed `dp[1]` (or every `dp[i]` with the item's own standalone value) and the answer is `max` over all `i`, not `dp[n]`. Reading `dp[n]` here is a classic wrong answer: it reports the best solution ending at the last element rather than the best overall. - **Two sequences, `dp[i][j]` over prefixes of lengths `i` and `j`.** Row `0` and column `0` describe one input being empty; they are seeded with the cost of consuming the other sequence from nothing, which is often a running total rather than a flat zero. - **Suffix states, `dp[i]` = the best answer over items `i..n`.** The base case moves to the far end (`dp[n+1]`) and the loop runs downward. The rule behind all of them is the same: **name the cell's meaning in one sentence, then derive the base case from that sentence rather than from habit.** If you cannot say out loud what `dp[0]` means, the table has no definition yet, and any bug you hit later will be argued about rather than diagnosed. ## In an interview Say the convention before you write the loop — "`dp[i]` is the answer over the first `i` items, so `dp[0]` is the empty prefix and it starts at the identity". It takes five seconds, it makes the base case obviously correct rather than a guess, and it removes the single most common source of arguing about indices for the rest of the session.