Base Cases and Initialization

A recurrence is a chain of dependencies. Base cases are the anchors that stop the chain. If they are wrong, every later state can be consistently wrong even when the transition looks perfect.

In Climbing Stairs, dp[0] = 1 because there is one way to do nothing. In Fibonacci, fib(0) = 0 because the sequence defines it that way. These look similar but have different meanings, which is why copying base cases across problems is dangerous.

Many DP problems need a state for the empty prefix, empty amount, or empty set. Edit Distance uses row zero and column zero for converting to or from the empty string. Coin Change II uses dp[0] = 1 because there is one way to make amount zero: choose no coins. Minimum Coin Change often uses dp[0] = 0 because zero coins are needed to make amount zero.

The empty state is not a hack. It is often the cleanest way to make the recurrence uniform.

For counting DPs, initialize impossible counts to 0 and seed the one known empty count when appropriate. For minimum DPs, initialize unknown states to a large sentinel so min works correctly. For maximum DPs, initialize impossible states to a very small sentinel if negative values are possible. For feasibility DPs, initialize boolean states to false except known true bases.

A common bug is leaving a Java integer array at zero for a minimum problem. Zero then looks like a valid best answer, causing impossible states to win.

Off-by-one errors usually come from unclear state meaning. If dp[i] means first i items, then item i - 1 is the newest item. If dp[i] means index i included in a zero-based array, then the newest item is i. Both are valid, but mixing them breaks transitions.

Before coding, decide whether your table includes an extra row or column for the empty prefix. Extra sentinel rows often make boundaries cleaner, especially in two-dimensional string DPs.