When you see a problem with random transitions, think probability DP. The pattern:
State: what you need to know (position, resources, moves left).
Transition: where is the probability of transition .
Base cases: terminal states where probability is or (or for ties). For counting paths, replace probability weights with counts. For expected values, weight by outcomes instead of just probabilities.