Lesson 54 — DP VIII: Counting With Constraints

~20 minutes · Day 70 · Decode Ways · Python

Tonight's problem is Decode Ways. Interviewers like it because it looks like plain counting, then quietly adds a rule: not every step is legal. A 0 cannot stand alone, 06 is not a letter, and only chunks from 1 to 26 count.

The invariant

Climbing stairs with a bouncer: a one- or two-digit step only counts when the chunk it consumes is a valid letter code (1-26, no leading zero).

That is the whole trick. This is still a one-dimensional DP chain, but each move must pass a validity test before it is allowed to add ways.

Decode Ways: the slow way first

The brute force is recursion: stand at index i, try consuming one digit, try consuming two digits, and count every path that reaches the end. Dynamic programming is built for this kind of repeated-subproblem counting (Wikipedia: dynamic programming).

def dfs(i):
    if i == len(s): return 1
    if s[i] == "0": return 0
    ways = dfs(i + 1)              # take one valid digit
    if i + 1 < len(s) and 10 <= int(s[i:i+2]) <= 26:
        ways += dfs(i + 2)         # take two valid digits
    return ways

This works, but it is O(2ⁿ) in the worst case: inputs like "111111" branch again and again into the same suffixes. The repeated question is: how many ways can the suffix starting at index i be decoded?

Decode Ways: the DP way

Let dp[i] mean: the number of ways to decode the suffix s[i:]. Python slices like s[i:i+2] read a short sequence chunk (Python docs: sequence operations). The answer lives at dp[0].

def num_decodings(s):
    n = len(s)
    dp = [0] * (n + 1)
    dp[n] = 1                       # empty suffix: one finished path
    for i in range(n - 1, -1, -1):
        if s[i] != "0":             # one digit: 1..9 only
            dp[i] += dp[i + 1]
        if i + 1 < n and 10 <= int(s[i:i+2]) <= 26:
            dp[i] += dp[i + 2]      # two digits: 10..26 only
    return dp[0]

Read the code as the four DP questions: state is dp[i], transition is valid one-step plus valid two-step, base is dp[n] = 1, answer is dp[0].

Transfer: same question, new digits

Before opening the reveal, predict the count for s = "11106". Say the two rules out loud: one digit must not be 0; two digits must be between 10 and 26.

What the trade buys you

The DP table pays memory to stop re-solving the same suffix. Later, this can compress to O(1) space because each state only reads two future states, but the full table is clearer for the first pass.

Practice — answer before you scroll past

if s[i] != "0":
    dp[i] += dp[i + 1]
if i + 1 < n and int(s[i:i+2]) <= 26:
    dp[i] += dp[i + 2]

Your move (tonight)

Solve Decode Ways in your Notion tracker using the cycle — predict → attempt → compare → encode.

1. Predict: write the state, transition, base case, and answer location before coding.
2. Attempt: code the table version from memory. If stuck, only reread the invariant.
3. Compare: watch the source below and find the exact sentence where your reasoning diverged.
4. Encode: add this invariant to your notes in your own words.

Stuck or curious? Ask your teacher (the agent) — that's what it's for.