State-Space Search as Shortest-Path DP

Sometimes DP is BFS/shortest path on an implicit graph of states—level order equals increasing cost steps.

Why this shows up in the real world

Puzzle sliders, word ladder with small alphabet.

Core idea (explained for students)

Use deque; visited set stores best distance to state key.

Try this in Python

from collections import deque


def min_steps_to_target(start: int, target: int) -> int:
    q = deque([(start, 0)])
    seen = {start}
    while q:
        x, d = q.popleft()
        if x == target:
            return d
        for y in (x + 1, x * 2):
            if 0 <= y <= 2 * target and y not in seen:
                seen.add(y)
                q.append((y, d + 1))
    return -1


print(min_steps_to_target(1, 10))

Common mistakes

• Re-enqueue worse costs—use if new < dist[key] guard.
• Huge branching factor.

Key takeaways

• Bidirectional BFS when goal is fixed.