You know how DP transitions work. dp[i] depends on previous cells. The formula connects everything.
But here's the thing: the formula tells you how cells RELATE. It never tells you where the chain STARTS.
That first cell gets filled before any transition runs. And if you get it wrong...
No crash. No error message. The table fills with confident, consistent, completely wrong values. And nothing tells you.
Coin Change COUNTING: How many ways to make amount N with coins 125? The DP table starts with a base case: dp[0] = 1. Let's see if the rest follows.
Every DP problem has the same question hiding at index 0 (or along the boundary): “What is the answer when the input is trivial?”
For counting problems, the trivial input has exactly ONE answer (the empty set). For minimization, the trivial input costs ZERO. For string transformations, the boundary cost equals the distance from “something” to “nothing.”
The transition formula is reusable machinery. The base case is where the problem's MEANING enters the table. Change the meaning, and every cell downstream changes with it — silently, confidently, and completely wrong.
Next time you write dp[0] = ..., don't reach for a template. Ask: “What does this state represent, and what is the answer to that question?”