Multi-State DP (Masks, Layers, Digit DP)

Encode extra booleans in the DP index—turn on lights, keys collected—state is (pos, mask) or (i, tight, started) for digit DP.

Why this shows up in the real world

Maze with keys shortest path. Tax reporting digit strings with leading zero rules.

Core idea (explained for students)

Cartesian product of small enums fits in table; keep transition table readable.

Try this in Python

def multi_state_paths(n: int, m: int) -> int:
    # count paths with at most one diagonal hop (toy)
    dp = [[[0, 0] for _ in range(m)] for _ in range(n)]
    dp[0][0][0] = 1
    for i in range(n):
        for j in range(m):
            for used in range(2):
                v = dp[i][j][used]
                if not v:
                    continue
                if i + 1 < n:
                    dp[i + 1][j][used] += v
                if j + 1 < m:
                    dp[i][j + 1][used] += v
                if i + 1 < n and j + 1 < m and used == 0:
                    dp[i + 1][j + 1][1] += v
    return sum(dp[-1][-1])


print(multi_state_paths(3, 3))

Common mistakes

• 2^20 without pruning—TLE.
• Forgetting to reset auxiliary flags between cases.

Key takeaways

• Symmetry breaking to shrink state (canonical order).