probability and expectation DP
Some processes involve chance: you roll a die and move that many squares, you flip coins until you see heads, a random walker steps left or right. Questions like 'what is the probability I reach the goal?' or 'how many steps on average until I finish?' are answered by DP where the table holds a probability or an expected value rather than a cost. The structure is familiar — break the problem into states and transitions — but the combining operation is a probability-weighted average, justified by the law of total expectation and the linearity of expectation.
The core tool is conditioning on the first random step. Let E[s] be the expected value of some quantity starting from state s. If from s the process moves to state s' with probability p(s -> s'), then E[s] = (immediate contribution) + sum over s' of p(s -> s') times E[s']. This is the law of total expectation: the overall expectation is the average of the conditional expectations, weighted by how likely each branch is. For probabilities it is the same shape with the immediate contribution dropped: Prob[reach goal from s] = sum over s' of p(s -> s') times Prob[reach goal from s']. A clean example: the expected number of fair-coin flips to get one head. Let E be that expectation; with probability 1/2 you get heads in one flip (done), and with probability 1/2 you waste a flip and are back where you started, so E = 1 + (1/2) E, giving E = 2. That self-reference is typical and is solved by algebra.
When the state graph is a DAG (no state can lead back to itself, directly or indirectly), you just evaluate states in reverse topological order, exactly like ordinary DP. The genuine complication is cycles: if states can revisit each other (as in the coin example, or random walks), the equations are mutually recursive and you cannot simply fill a table in one pass — you must solve a system of linear equations, by substitution for small cases or Gaussian elimination in general. A common pitfall is treating an expectation problem as if it had a clean acyclic order when the process can loop; another is forgetting that linearity of expectation lets you sum expected contributions even when the underlying events are dependent, which often dramatically simplifies the state.
Expected rolls of a fair six-sided die until you first see a 6. Let E be that expectation. With probability 1/6 you succeed on this roll; with probability 5/6 you waste a roll and start over: E = 1 + (5/6) E, so (1/6) E = 1 and E = 6. The self-referential equation captures the loop exactly.
Condition on the first step; acyclic states fill in topological order, cyclic ones need a linear solve.
If the random process can loop back to a state, the DP equations are mutually recursive — you must solve them as a linear system, not fill a table in one sweep; only acyclic state graphs let you evaluate in topological order.