Probability DP

At a glance

The instinct

Counting DP asks "how many ways"; probability DP asks "what fraction of ways" - and when each outcome has a known chance you simply weight each transition by it. Two directions work:

• Forward (push): start with probability 1 at the start state and, each step, pour every state's mass into its successors, multiplied by each outcome's chance. Good when you know where you start and how many steps to take.
• Backward (pull): define f(state) = probability of success (or expected cost) from this state, and write f(state) = Σ p(outcome) · f(next). Good when the process stops at absorbing states and you need the answer from the start.

Recognise it

Not this pattern if...

• The answer is a count of outcomes modulo 1e9+7 - that is counting DP or combinatorics (divide later if needed).
• The randomness is in the algorithm (shuffle, reservoir sampling) and you just need to implement it.
• A closed form is obvious (e.g. symmetric dice sums) and the interviewer wants the math, not the table.

Memory hack

Analogy: a Galton board (the pegboard where balls bounce left or right). You never follow one ball - you track what fraction of all balls sits in each slot after each row of pegs.

DP framing:

• State - (step, position) for forward problems; (remaining resources) for backward ones.
• Choice - nature's choice, not yours: every outcome happens, weighted by its probability (for "optimal play under randomness", take max over your move of the weighted average).
• Base case - forward: P[0][start] = 1. Backward: absorbing states have fixed values (1 for success, 0 for failure, 0 expected cost at the goal).
• Order - forward by step count; backward from states closer to absorption, or memoised recursion.

Say it out loud in the interview:

1. "Each step has these outcomes with these probabilities; they sum to 1."
2. "I'll push probability forward step by step (or pull success probability backward from the end)."
3. "Mass that leaves the valid region is dropped; my answer sums the mass in the target states."

How it works

Worked trace for New 21 Game with k = 2, maxPts = 3, n = 3. p[x] = probability that the running total ever equals x. Only totals below k keep drawing, so p[x] = (sum of p[x-maxPts .. x-1] restricted to totals < k) / maxPts. Keep that sum as a sliding window.

Sanity check: drawing 2 or 3 immediately (2/3) or drawing 1 and then 1 or 2 (1/3 · 2/3 = 2/9) gives 8/9.

Java template

import java.util.*;

class ProbabilityDp {
    // 1) Forward push: probability of still being "alive" after k random moves.
    static double surviveProbability(int n, int k, int startR, int startC, int[][] moves) {
        double[][] cur = new double[n][n];
        cur[startR][startC] = 1.0;                         // base case: all mass at the start
        for (int step = 0; step < k; step++) {
            double[][] nxt = new double[n][n];
            for (int r = 0; r < n; r++) {
                for (int c = 0; c < n; c++) {
                    if (cur[r][c] == 0) continue;
                    double share = cur[r][c] / moves.length;   // uniform outcomes; use weights if not
                    for (int[] m : moves) {
                        int nr = r + m[0], nc = c + m[1];
                        if (nr >= 0 && nr < n && nc >= 0 && nc < n) nxt[nr][nc] += share; // else: spilled
                    }
                }
            }
            cur = nxt;
        }
        double total = 0;
        for (double[] row : cur) for (double v : row) total += v;
        return total;
    }

    // 2) Sliding-window absorption: draw 1..w uniformly while total < k; P(final total <= n).
    static double stopWithin(int n, int k, int w) {
        if (k == 0 || n >= k - 1 + w) return 1.0;         // every possible stop is <= n
        double[] p = new double[n + 1];
        p[0] = 1.0;
        double window = 1.0, answer = 0.0;                 // window = mass of live totals in [x-w, x-1]
        for (int x = 1; x <= n; x++) {
            p[x] = window / w;
            if (x < k) window += p[x]; else answer += p[x]; // live totals keep drawing; others stop
            if (x - w >= 0 && x - w < k) window -= p[x - w];
        }
        return answer;
    }
}

Complexity

Variations

• Fixed-step forward push - probability of staying inside a region after K moves. Knight Probability in Chessboard, Out of Boundary Paths (the counting twin).
• Backward memo with absorbing states - recurse on remaining resources; for huge inputs notice the answer converges and short-circuit. Soup Servings (scale by 25 ml; for large n the answer is effectively 1).
• Sliding-window probabilities - transitions from a contiguous range of states. New 21 Game.
• Knapsack over coins - dp[i][h] = probability of h heads after i coins. Toss Strange Coins.
• Expected value with self-loops - E = 1 + q · E solves to E = 1 / (1 - q); move the self term to the left before iterating.
• Probability + optimal choice - take max over your action of the expected outcome (Markov decision style), e.g. dice games where you choose to stop or continue.

Common mistakes

• Tracking counts instead of probabilities: 8^K knight paths overflow quickly, while probabilities stay in [0, 1].
• Dividing by the number of valid moves instead of all moves - an off-board move still "uses up" its 1/8.
• Comparing doubles with == in tests or termination checks; use a tolerance like 1e-9.
• Off-by-one in sliding windows: the window must hold only states that are still drawing (< k).
• Running a backward recursion on inputs as large as 10^9 without spotting convergence or scaling.

All practice problems

3 problems on this site use this pattern, easiest first. Solve them in order and say the instinct out loud before you code.