I Couldn't See Why dp[i] = dp[i+1] + dp[i+2] Actually Counts Anything

I've been working through coding problems that I can understand when reading solutions but struggle to solve on my own. This series is about breaking down the "why does this actually work" part. Not tutorials. Just honest breakdowns of where my thinking got stuck and what finally unstuck it.

The problem

LeetCode 91: Decode Ways. You get a string of digits. Each digit or pair of digits maps to a letter (1 = A, 2 = B, ... 26 = Z). Count how many ways you can decode the entire string.

When I first read this, I thought: find all the different permutations and combinations of the input string, filter out the ones that are one or two digits, count them. If it starts with 0, return 0.

That's wrong in a very specific way. The string order is fixed. You never rearrange anything. You're deciding where to place the splits.

Partitioning, not permutations

Take "226". You're not shuffling characters around. You're choosing how to chop the string into consecutive pieces, left to right, where each piece is one or two digits between 1 and 26.

• 2 | 2 | 6 → B, B, F
• 22 | 6 → V, F
• 2 | 26 → B, Z

Three ways. Every digit is used exactly once. Every piece is consumed in order.

This seems obvious once you see it, but my first instinct was to think about substrings and combinations. The shift to "I'm just deciding where to put dividers in a fixed sequence" changed how I thought about the whole problem.

The binary choice at each position

Once partitioning clicks, the structure gets simple. At every position in the string, you have exactly two options: take one digit or take two digits. That's it. Then you repeat from wherever you land.

At position 0 of "226":

• Take "2" (one digit) → now you're at position 1 with "26" remaining
• Take "22" (two digits) → now you're at position 2 with "6" remaining

Each of those remaining strings has its own set of choices. If you draw this out, it forms a binary tree. Every path from the root to a leaf where you've consumed the entire string is one valid partition.

I could see this. I could draw the tree. I could count partitions by hand. What I could not figure out was why the DP formula dp[i] = dp[i+1] + dp[i+2] actually produces the right count. It looked like it should work. I could verify it on examples. But I couldn't explain why.

The part where I got stuck

The DP says: dp[i] is the number of ways to decode the string starting from position i. Fill right to left. Base case: dp[n] = 1 (you've consumed everything, that counts as one completed partition).

The recurrence:

dp[i] = 0
if s[i] != '0':           dp[i] += dp[i+1]   # take 1 digit
if s[i:i+2] is 10–26:     dp[i] += dp[i+2]   # take 2 digits

I could fill in the array mechanically. For "1226":

dp[4] = 1
dp[3] = 1
dp[2] = 2
dp[1] = 3
dp[0] = 5

Correct answer: 5. But why does adding two values from the right give you the count of all partitions? I stared at visual walkthroughs and formula breakdowns and nothing was landing.

What actually made it click: the addition principle

The breakthrough had nothing to do with DP specifically. It came from a much more basic idea.

You have 3 red shirts and 2 blue shirts. How many shirts can you pick? You say 3 + 2 = 5. This works because no shirt is both red and blue. The groups don't overlap.

That's the addition principle. If you can split a counting problem into non-overlapping groups, the total count is the sum of the group counts.

Now, at position i in the string, every partition that passes through this position does exactly one of two things: it takes one digit or it takes two digits. Not both. These are two non-overlapping groups.

• Group A (took one digit): all partitions where the first chunk starting at i is a single digit. How many partitions are in this group? However many ways you can finish the rest of the string from position i+1. That's dp[i+1].

• Group B (took two digits): all partitions where the first chunk starting at i is a two-digit number. How many? However many ways to finish from position i+2. That's dp[i+2].

Every partition is in exactly one group. No overlap, no gaps. So the total is the sum: dp[i] = dp[i+1] + dp[i+2].

That's it. The addition isn't some DP trick. It's the same logic as counting shirts. You're splitting the partitions into two non-overlapping groups based on the choice made at this position.

Addition vs. multiplication (and why this matters for other DP problems)

While working through this, I realized the addition principle has a sibling that shows up in different DP problems: the multiplication principle.

Addition: you're choosing between alternatives. Red shirt OR blue shirt. Take 1 digit OR take 2 digits. The groups compete for one slot. You add.

Multiplication: you're combining independent sequential choices. Pick a shirt AND pick pants. 3 shirts × 4 pants = 12 outfits. The choices don't compete. They stack.

The question to ask yourself at each step of a DP recurrence: "Am I looking at alternatives (OR) or combinations (AND)?"

Decode ways is pure OR. At each position, you do one thing or the other. So the formula is a sum.

Something like "how many n-character PINs can you make with 5 vowels for position 1 and 10 digits for position 2?" is pure AND. You need both positions filled, every vowel pairs with every digit. So it's a product: dp[i] = dp[i-1] × choices[i].

The paint fence problem (no three consecutive posts the same color) uses both. At each post, the total splits into two groups (same as previous OR different from previous, that's addition). Within the "different" group, each valid history combines with each color choice (that's multiplication). So the recurrence has both: diff[i] = (same[i-1] + diff[i-1]) × (k-1).

Recognizing which principle applies at each piece of a recurrence is what turns "I can verify it works" into "I understand why it works."

The base case makes sense now too

dp[n] = 1 confused me initially. You're past the end of the string. There's nothing left. Why is that 1 and not 0?

Because it's the "I made it" signal. If a path of choices led you all the way past the last digit, that path consumed everything and represents one complete partition. If dp[n] were 0, every path would add up to 0 and nothing would ever get counted.

Think of it like the road fork analogy. If you take a path and it leads to an exit, that exit counts as 1. The exit existing is what makes the path worth counting.

The direction question

One more thing that wasn't obvious: why fill right to left?

It depends on how you define dp[i]. I defined it as "ways to decode from position i to the end." That means dp[i] depends on dp[i+1] and dp[i+2], both of which are to the right. So those need to exist before you compute dp[i]. Right to left.

But you could define it the other way: dp[i] = ways to decode from the start up to position i. Now your answer at i depends on dp[i-1] and dp[i-2], both to the left. Fill left to right. Same final answer, different direction.

The direction isn't a property of the problem. It's a property of how you phrase the question dp[i] is answering. "How many ways to get here?" looks backward. "How many ways from here to the end?" looks forward.

The code

class Solution:
    def numDecodings(self, s: str) -> int:
        n = len(s)
        dp = [0] * (n + 1)
        dp[n] = 1

        if s[n - 1] != '0':
            dp[n - 1] = 1

        for i in range(n - 2, -1, -1):
            if s[i] != '0':
                dp[i] += dp[i + 1]
            two_digit = int(s[i:i + 2])
            if 10 <= two_digit <= 26:
                dp[i] += dp[i + 2]

        return dp[0]

Practice problems

In order of difficulty, all using similar DP thinking:

1. LeetCode 70 (Climbing Stairs): Same recurrence structure as decode ways but without validity checks. Pure dp[i] = dp[i-1] + dp[i-2]. Good for building muscle memory on the pattern.
2. LeetCode 198 (House Robber): 1D DP with "take or skip" choices at each position. The OR/addition principle applies the same way.
3. LeetCode 256 (Paint House): Tracking states (which color was last used) similar to the paint fence same/diff tracking. Uses both addition and multiplication thinking.
4. LeetCode 639 (Decode Ways II): Decode ways but with wildcard characters. Same core logic, more validity branches to handle.

I'm building Levelop to help people get better at problems like these. If you want more breakdowns like this, check it out.