LeetCode 3548: Count Good Integers on Path — Digit DP Visualized Step by Step

#leetcode #algorithms #python #dynamicprogramming

If you've ever stared at a Digit DP solution and thought "I have no idea what's happening inside that recursion" — this one's for you.

We'll break down LeetCode 3548 step by step, trace through the memoization table as it builds up, and actually see how the DP states evolve.

The Problem

Given integers l, r, and a string directions consisting of 'D' (down) and 'R' (right), imagine a 4x4 grid. You start at (0,0) and follow the directions to trace a path. Each cell maps to a digit position in a 16-digit number.

Count how many integers in [l, r] have non-decreasing digits along the path.

Why This Is Hard to Debug

Digit DP is notoriously confusing because:

The state space is abstract: (index, is_tight, last_value)
The recursion tree is deep (16 levels)
The memo table fills up in a non-obvious order
A single wrong condition silently gives the wrong count

Step 1: Map the Path

Before any DP, we need to know which digit positions lie on the path.

path_set = set()
row, col = 0, 0
path_set.add(0)  # starting position
for d in directions:
    if d == 'D':
        row += 1
    else:
        col += 1
    path_set.add(row * 4 + col)

For directions = "DDRR", the path visits cells (0,0) → (1,0) → (2,0) → (2,1) → (2,2), which map to 1D indices {0, 4, 8, 9, 10}.

These are the positions where the non-decreasing constraint applies. All other positions are "free" — any digit works.

Step 2: The Digit DP Framework

We count how many valid 16-digit numbers exist from 0 to some limit:

def count_valid(limit: int) -> int:
    limit_str = str(limit).zfill(16)
    memo = {}

    def dp(idx, is_tight, last_val):
        if idx == 16:
            return 1

        state = (idx, is_tight, last_val)
        if state in memo:
            return memo[state]

        res = 0
        upper_bound = int(limit_str[idx]) if is_tight else 9

        for d in range(upper_bound + 1):
            if idx in path_set:
                if d >= last_val:
                    res += dp(idx + 1, is_tight and (d == upper_bound), d)
            else:
                res += dp(idx + 1, is_tight and (d == upper_bound), last_val)

        memo[state] = res
        return res

    return dp(0, True, 0)

The answer is count_valid(r) - count_valid(l - 1).

Understanding the Three States

State	Meaning
`idx`	Current digit position (0–15)
`is_tight`	Are we still bounded by `limit`? If the prefix so far equals `limit`'s prefix, we can't exceed `limit[idx]`. Once we go lower, we're "free" (`is_tight = False`) and can use digits 0–9.
`last_val`	The last digit placed at a path position. The next path digit must be `>= last_val`.

The Key Branching Logic

if idx in path_set:
    # This position is on the path — enforce non-decreasing
    if d >= last_val:
        res += dp(idx + 1, ..., d)  # update last_val
else:
    # Not on the path — no constraint, last_val unchanged
    res += dp(idx + 1, ..., last_val)

This is where most bugs happen. Common mistakes:

Updating last_val for non-path positions
Using > instead of >= (strictly increasing vs non-decreasing)
Forgetting to check is_tight when computing upper_bound

Step 3: Tracing Through the Memo Table

Let's trace count_valid(20) with path_set = {0, 4, 8, 9, 10}.

The recursion starts at dp(0, True, 0). Position 0 is on the path, limit_str = "0000000000000020", so upper_bound = 0.

Only d = 0 is valid (it's >= last_val = 0). We recurse to dp(1, True, 0).

Position 1 is not on the path. upper_bound = 0 (still tight). We place d = 0 freely and move on.

This continues until we hit position 4 (on the path again). Now the interesting branching starts.

The memo table builds bottom-up as recursion returns:

(15, True, 0) → 1    # base case: only one way to "finish"
(14, True, 0) → 1    # one digit left, tight, only d=0 works
...
(8, True, 0)  → 10   # position 8 is on path, branching begins
(4, True, 0)  → 10   # accumulated from subtree
(0, True, 0)  → 10   # final answer for count_valid(20)

The is_tight = False states are where the count explodes — once we go below the limit, we have full freedom for remaining digits.

Step 4: Putting It Together

return count_valid(r) - count_valid(l - 1)

For l = 10, r = 20:

count_valid(20) = 10
count_valid(9) = ?
Answer: the difference

Tips for Digit DP Problems

Always pad with leading zeros — str(limit).zfill(width) prevents off-by-one issues with shorter numbers.
The is_tight flag is the hardest part — draw out what happens when you're at the boundary vs. free. Once is_tight becomes False, it stays False for all deeper calls.
Trace the memo table — don't just read the code. Watch how states fill up. The order matters for understanding what each cached value represents.
Test with small inputs first — l=1, r=9 should be trivially verifiable by hand before you try larger ranges.