Pattern - Probability DP

When you see a problem with random transitions, think probability DP. The pattern:

$1.$ State: what you need to know (position, resources, moves left).

$2.$ Transition: $dp[state] = \sum p_i \cdot dp[next_i]$ where $p_i$ is the probability of transition $i$.

$3.$ Base cases: terminal states where probability is $0$ or $1$ (or $0.5$ for ties). For counting paths, replace probability weights with counts. For expected values, weight by outcomes instead of just probabilities.