Modeling DP State Transitions

The recurrence edge from -> to with weight or count—write all legal predecessors explicitly when debugging.

Why this shows up in the real world

Finite automaton minimal word acceptance is DP over states and input index.

Core idea (explained for students)

Template: new[to] += sum(old[from] for from in preds(to)).

Try this in Python

def markov_two_state(p00: float, p11: float, steps: int) -> list[float]:
    # prob being in state0 after steps
    dp0, dp1 = 1.0, 0.0
    for _ in range(steps):
        nd0 = dp0 * p00 + dp1 * (1 - p11)
        nd1 = dp0 * (1 - p00) + dp1 * p11
        dp0, dp1 = nd0, nd1
    return [dp0, dp1]


print([round(x, 3) for x in markov_two_state(0.7, 0.6, 5)])

Common mistakes

• Missing transition for boundary characters.
• Double counting paths without DAG property.

Key takeaways

• Draw small graph picture for states 0..S-1.