Pattern Guide
Probability & Expected Value DP
"E[X] = Σ p(outcome) × value(outcome). DP builds it up iteratively."
Probability problems compute the expected value or probability of an outcome through a series of random choices. DP works because expected value decomposes: E[reaching state i] depends on E[reaching predecessor states]. Learn the gambler's ruin, dice throws, and random walk patterns.
Problems you can solve with this pattern
5 problems · click any to start solving
// ===== FORWARD DP: "probability of being in state s at step t" =====
// dp[t][s] = probability of being in state s after t steps
// Transition: dp[t+1][s'] += dp[t][s] * P(s → s')
// ===== BACKWARD DP: "expected cost to reach goal from state s" =====
// dp[s] = E[cost to reach goal | starting at state s]
// Transition: dp[s] = Σ P(s → s') * (cost(s→s') + dp[s'])
// Base: dp[goal] = 0 (already at goal, no more cost)
// Example: Knight on an infinite board, probability of staying on an 8x8 board
// after k moves — forward DP:
function knightProbability(n, k, row, col) {
const moves = [[2,1],[2,-1],[-2,1],[-2,-1],[1,2],[1,-2],[-1,2],[-1,-2]];
let dp = Array.from({length:n},()=>new Array(n).fill(0));
dp[row][col] = 1.0;
for (let m = 0; m < k; m++) {
const next = Array.from({length:n},()=>new Array(n).fill(0));
for (let r=0;r<n;r++)
for (let c=0;c<n;c++) {
if (!dp[r][c]) continue;
for (const [dr,dc] of moves) {
const nr=r+dr, nc=c+dc;
if (nr>=0&&nr<n&&nc>=0&&nc<n)
next[nr][nc] += dp[r][c] / 8;
}
}
dp = next;
}
return dp.reduce((s,row)=>s+row.reduce((a,b)=>a+b,0), 0);
}Probability DP uses the linearity of expectation: E[X + Y] = E[X] + E[Y]. At each state, we compute either the probability of reaching it or the expected value starting from it. The key: transitions are probabilistic. Instead of "take min of neighboring states," we sum probabilities or expected values weighted by transition probabilities.
Two Directions of DP
// ===== FORWARD DP: "probability of being in state s at step t" =====
// dp[t][s] = probability of being in state s after t steps
// Transition: dp[t+1][s'] += dp[t][s] * P(s → s')
// ===== BACKWARD DP: "expected cost to reach goal from state s" =====
// dp[s] = E[cost to reach goal | starting at state s]
// Transition: dp[s] = Σ P(s → s') * (cost(s→s') + dp[s'])
// Base: dp[goal] = 0 (already at goal, no more cost)
// Example: Knight on an infinite board, probability of staying on an 8x8 board
// after k moves — forward DP:
function knightProbability(n, k, row, col) {
const moves = [[2,1],[2,-1],[-2,1],[-2,-1],[1,2],[1,-2],[-1,2],[-1,-2]];
let dp = Array.from({length:n},()=>new Array(n).fill(0));
dp[row][col] = 1.0;
for (let m = 0; m < k; m++) {
const next = Array.from({length:n},()=>new Array(n).fill(0));
for (let r=0;r<n;r++)
for (let c=0;c<n;c++) {
if (!dp[r][c]) continue;
for (const [dr,dc] of moves) {
const nr=r+dr, nc=c+dc;
if (nr>=0&&nr<n&&nc>=0&&nc<n)
next[nr][nc] += dp[r][c] / 8;
}
}
dp = next;
}
return dp.reduce((s,row)=>s+row.reduce((a,b)=>a+b,0), 0);
}- "What's the probability of X after k steps?" → forward DP, spread probability each step
- "Expected number of steps to goal?" → backward DP, E[s] = 1 + average E[neighbors]
- "Probability of outcome given constraints?" → forward DP on score/state, sum valid final states
- "Sliding window probability" → use running sum to avoid O(n²) per transition
Key insight: For probability DP, instead of taking min/max of neighboring states, you AVERAGE them (weighted by transition probabilities). E[s] = Σ p(s→s') * (cost + E[s']).