Probability DP applies to problems where outcomes depend on random events and the answer is an expected value or a probability. The table stores "the probability of being in state X after t steps," and values propagate by multiplying each predecessor's probability by its transition probability, then summing:

dp[step][state] = sum of (dp[step-1][prev_state] * probability of moving from prev_state to state)

Consider a state D that can be reached from three previous states A, B, C. The probabilities below are the layer-t-1 probability of each predecessor (these sum to 1 over the full predecessor layer), and the edge labels are the transition probabilities into D.

State D's probability = (0.5 0.4) + (0.3 0.5) + (0.2 0.25) = 0.20 + 0.15 + 0.05 = 0.40*

Each incoming edge contributes a fraction of its source state's probability. A, B, and C will have other outgoing transitions to states besides D; only the edges into D matter for computing dp[t][D].

Not every problem with the word "probability" needs DP. A combination of the following signals points to Probability DP:

If the problem asks "what is the probability after k steps" and the number of states is bounded, a DP table indexed by (step, state) is the right structure. Common shapes: random walks on grids, dice/coin games, absorbing Markov chains, and expected-value problems.

A general framework for the recurrence:

State definition:

dp[t][s] = the probability of being in state s after exactly t steps

Base case:

dp[0][start] = 1.0 (the starting position has all the probability mass), and dp[0][anything else] = 0.0

Transition:

For each state s at step t, look at all states that could transition into s:

dp[t][s] = sum over all predecessors p of (dp[t-1][p] * transition_probability(p, s))

Answer:

Sum dp[k][s] over all "valid" or "desired" states s after k steps.

The probability leak. In many problems, some transitions lead to invalid states (like a knight moving off the board). The probability that would have gone to that state disappears from the table, so after k steps the sum of dp[k][all valid states] is less than or equal to 1.0. The gap between this sum and 1.0 is the probability that the process ended up in an invalid state at some point.

After step 2, only 0.56 probability remains on valid states, so there is a 0.44 chance the knight fell off at some point.

Problem Statement

You are given an n x n chessboard and a knight at position (row, column). The knight makes exactly k moves. In each move, it picks one of its 8 possible L-shaped moves uniformly at random (each with probability 1/8). Find the probability that the knight remains on the board after all k moves.

Approach

Let dp[t][r][c] be the probability that the knight is at cell (r, c) after exactly t moves and has never left the board. An off-board knight contributes zero to all future steps.

Step-by-Step Trace

Trace a small example: n = 3, k = 2, starting position (0, 0).

Step 0: Initial state

The knight is at (0, 0) with probability 1.0. All other cells have probability 0.

Step 1: After 1 move

From (0, 0), the 8 possible knight moves are (1,2), (2,1), (-1,2), (-2,1), (1,-2), (2,-1), (-1,-2), (-2,-1). On a 3x3 board, only (1,2) and (2,1) are valid. Each gets 1.0 * (1/8) = 0.125.

Total on-board probability = 0.25. After step 1, there is a 0.75 chance the knight has fallen off the board.

Step 2: After 2 moves

From (1, 2) with P = 0.125: valid destinations on the 3x3 board are (0,0) and (2,0). Each gets 0.125 * (1/8) = 0.015625.

From (2, 1) with P = 0.125: valid destinations are (0,0) and (0,2). Each gets 0.125 * (1/8) = 0.015625.

(0,0) received contributions from both (1,2) and (2,1), so 0.015625 + 0.015625 = 0.03125.

Total on-board probability after 2 moves = 0.03125 + 0.015625 + 0.015625 = 0.0625

The answer is 0.0625, or 1/16.

Implementation

Only the previous step's values are needed to compute the current step, so two 2D arrays suffice. Swap them each iteration to keep space at O(n^2) instead of O(k * n^2).

Complexity Analysis

The Knight Probability used a forward formulation: each layer was a time step. New 21 Game uses a backward formulation, and it introduces a sliding-window optimization that turns an O(n * w) DP into O(n). The pattern is "the recurrence is a uniform sum over a contiguous range, so maintain the sum incrementally."

Problem Statement

Alice plays a game. Her score starts at 0. While her score is strictly less than k, she draws a uniformly random integer from [1, w] and adds it to her score. She stops as soon as her score reaches k. Return the probability that her final score is at most n.

Concretely: k = 17, n = 21, w = 10. The answer is approximately 0.7327.

Setting Up The DP

The natural state is the current score. Let dp[s] be the probability of finishing with score at most n, given that the current score is s.

dp[s] = (1/w) * (dp[s+1] + dp[s+2] + ... + dp[s+w])

The answer is dp[0]. Iterate s from k - 1 down to 0, computing each cell using the next w cells.

Direct DP Implementation

This is O(k * w) time. For LC 837 with k, w up to 10^4, that is 10^8 operations, borderline but acceptable. The next step is to notice that the inner sum can be maintained incrementally.

The Sliding Window Optimization

When iterating from s = k - 1 down to s = 0, the windows [s+1, s+w] for consecutive values of s overlap by w - 1 entries. Going from s to s - 1:

So we maintain a running sum windowSum and update it in O(1) per cell:

Time drops to O(k + w). For k = w = 10^4, that is 2 * 10^4 operations.

Why The Sliding-Window Step Is Correct

When we compute dp[s] = windowSum / w, windowSum is the sum of dp[s+1] ... dp[s+w]. Immediately after we write dp[s], we update windowSum so that it now represents the sum of dp[s] ... dp[s+w-1], which is the window we need for the next iteration at s - 1. The update windowSum += dp[s] - dp[s + w] does exactly this: adds the new low end, drops the old high end.

The guard n >= k + w - 1 is a correctness short-circuit. Alice's last action is a draw from some starting score s ≤ k - 1, and the largest possible final score is (k - 1) + w. If n ≥ k + w - 1, every possible final score is ≤ n, so the answer is exactly 1. The DP would still return 1 here (since every terminal cell dp[s] for s in [k, k+w-1] would be 1), but checking up front avoids the floating-point sum that can drift slightly off 1.0 for large k and w.

When To Look For This Optimization

Look for the sliding-window trick whenever a probability or expectation DP has a recurrence of the form:

dp[s] = (1 / w) * sum over d in [a, b] of dp[s + d]

where the sum is over a window of consecutive states with uniform weights. The window slides by one as s decreases, and the running sum can be maintained in O(1) per step.

This pattern also appears outside probability DP: Number of Ways to Stay in the Same Place After Some Steps, Domino and Tromino Tiling variants, and others have a uniform-window structure that admits the same optimization. The signal is "the same coefficient applied across a fixed-width range of neighbors."

Complexity Analysis

So far the DP stored a probability at each state: the chance the system is in that state. A closely related family stores an expected value at each state: the average of some quantity conditioned on starting there. The two share the same recurrence shape, but the semantics are different, and confusing them is a common bug in this area.

Probability vs. Expectation

For a random process with states s:

The arrow of time is opposite in the two formulations. Probability flows forward from the start. Expectation flows backward from the terminal states, where E[terminal] = 0 (or some known terminal value).

When To Reach For Each

A useful sanity check: if the answer's unit is a probability (a dimensionless number in [0, 1]), use the probability formulation. If the answer's unit matches the quantity being averaged (rolls, dollars, length), use the expectation formulation.

Linearity of Expectation: Sometimes No DP Is Needed

Before writing a DP, check whether linearity of expectation collapses the problem. If the answer is the sum of independent (or even dependent) contributions, the expectation is the sum of the per-contribution expectations.

Example: expected number of rolls of a fair six-sided die until the first 6 appears. Each roll succeeds with probability 1/6, so the expected number of rolls is the mean of a geometric distribution: 1 / (1/6) = 6. No DP, no recurrence, no table.

This is worth checking because many "expected something" problems have closed-form answers via linearity. DP enters when the contributions are not independent or when the stopping condition couples them.

Worked Example: Expected Rolls To Reach A Target Sum

Problem. Start with sum s = 0. Repeatedly roll a fair six-sided die and add the result to s. Stop when s >= N. What is the expected number of rolls?

Linearity does not give a clean answer here because the stopping condition depends on the running sum. Set up an expectation DP.

E[s] = 1 + (1/6) * (E[s+1] + E[s+2] + E[s+3] + E[s+4] + E[s+5] + E[s+6])

Because E[s] depends on E[s+1] ... E[s+6], we fill the table from large s down to s = 0. This backward direction is the defining feature of expectation DP.

For N = 10, this returns approximately 3.0265. As a sanity check, the expected die value is 3.5, so reaching s = 10 should take roughly 10 / 3.5 ≈ 2.86 rolls. The DP value is slightly larger because of overshoot near the boundary, which the DP captures exactly.

Forward vs. Backward DP

The Knight Probability code in the previous section runs forward: it builds layer t of probabilities from layer t-1. The expected-rolls code above runs backward: it builds E[s] from E[s+1..s+6].

Both directions are valid for both formulations, but conventions exist:

When choosing, ask: "Is the answer a property of one state (E[start]), or a sum over many states (Σ P[final])?" The former is usually backward; the latter is usually forward.

Common Pitfalls

Probability DP and expectation DP are the same machinery applied to different questions. Once the recurrence shape is matched to the question, the rest is bookkeeping: which direction to fill, which terminals to seed, and which final state holds the answer.