Knight Probability LeetCode 688 — DP Guide

LeetCode 688 Knight Probability in Chessboard gives you an n×n chessboard, a starting position (row, col), and a number of moves k. A knight makes exactly k moves. At each move, it picks uniformly at random from up to 8 L-shaped directions: (±1, ±2) and (±2, ±1). If a chosen direction moves the knight off the board, it lands off permanently and contributes zero to on-board probability. You must return the probability that the knight is still on the board after exactly k moves.

The problem combines grid traversal with probability computation. A knight at a corner has only 2 valid moves; at an edge it may have 3 or 4; at an interior cell it has all 8. Each valid move is chosen with equal probability 1/8 regardless of how many valid neighbors exist. Moves off the board are still chosen — they just remove the knight from play. This means the total probability decreases with each step unless the knight is always at an interior cell.

Understanding the probability model precisely is essential before writing any DP. The knight does not "avoid" off-board moves — it picks one of 8 directions uniformly, and some of those 8 directions may leave the board. So the probability of staying on board for a single move from an interior cell is 8/8 = 1, but from a corner cell it is 2/8 = 0.25. The overall answer accumulates these per-step survival probabilities across k moves.

A brute-force simulation traces every possible sequence of k moves from the starting position. At each step, branch into up to 8 directions, discard off-board branches, and recurse. The total number of paths is at most 8^k — for k=100, that is an astronomically large number. Even with pruning for off-board branches, the tree is far too large for direct simulation. This approach is exponential in k and completely infeasible.

Dynamic programming works because the paths have massive overlap. After 3 moves, the knight might reach cell (2, 3) via dozens of different route combinations. Each of those routes contributes some probability mass to (2, 3). Instead of tracking individual paths, DP accumulates the total probability of being at each cell after each step. The probability at cell (r, c) after step t depends only on the probabilities at cells reachable in one move from (r, c) in step t-1 — a clean recurrence with no path enumeration.

The key mental shift is to think forward: start with probability 1.0 at (row, col) after 0 moves, then propagate probability mass outward through each of the 8 knight moves at each step. After k steps, sum up all probability values still on the board. This is exactly the DP formulation. It turns an exponential path-counting problem into an O(k·n²) grid update.

Define dp[step][r][c] as the probability that the knight is at cell (r, c) after exactly step moves. The base case is dp[0][row][col] = 1.0 and dp[0][r][c] = 0.0 for all other cells. The transition propagates probability forward: for each cell (r, c) with dp[step-1][r][c] > 0, and for each of the 8 knight move directions (dr, dc), if (r+dr, c+dc) is on the board, then dp[step][r+dr][c+dc] += dp[step-1][r][c] / 8.

This forward-propagation recurrence is natural for probability problems. At each step, you distribute the probability mass at each cell equally among all 8 knight-move destinations. Destinations off the board simply receive no probability — their mass is lost. After all k steps, the answer is the sum of dp[k][r][c] over all valid (r, c). Equivalently, you can propagate backward (pull from neighbors), but the forward direction maps more cleanly to the mental model of probability flowing outward.

The 3D table has dimensions (k+1) × n × n, giving O(k·n²) space. For n=25 and k=100, this is about 62,500 floating-point values — small enough to fit comfortably in memory. Time complexity is O(k·n²·8) = O(k·n²) since the 8-direction loop is constant. Both bounds are well within the problem constraints.

The 3D DP table stores all k+1 layers simultaneously, but the transition from step t only depends on step t-1. This means only two 2D arrays are needed at any time: the previous step's board and the current step's board. After computing the current step, the previous step can be discarded. This reduces space from O(k·n²) to O(n²) — a factor-of-k improvement with no change in time complexity.

In practice, use two n×n arrays: prev and curr. Initialize prev with 1.0 at (row, col). For each step, zero out curr, then iterate all cells in prev and propagate probability to valid knight-move destinations in curr. After each step, swap prev and curr (or copy curr into prev). After k steps, the answer is the sum of all values in prev.

The swap pattern is more cache-friendly than allocating new arrays each step. In Python, a tuple swap prev, curr = curr, prev works elegantly. In Java, maintain two 2D double arrays and alternate which one is "current." This optimization is straightforward to implement once the 3D formulation is clearly understood — the 3D version is easier to reason about first, and the 2D optimization is a direct mechanical reduction.

The boundary condition in this problem is unusually clean: moves that go off the board simply do not happen in the DP table. When propagating probability from (r, c), check if (r+dr, c+dc) satisfies 0 ≤ nr < n and 0 ≤ nc < n. If not, skip that direction — no probability is added anywhere. The probability that went "off the board" is not redistributed; it is simply lost, which correctly models the knight leaving play.

There is no need for sentinel values, padding, or extra rows and columns. The bounds check replaces any special-case handling. This contrasts with problems like Minimum Path Sum where boundary cells have fewer valid predecessors and need explicit initialization. In Knight Probability, every cell always has exactly 8 candidate moves — some subset of which are valid based on position — and the bounds check handles all cases uniformly.

One subtle point: the probability at off-board positions is implicitly zero and never stored. The sum of all on-board probabilities after k steps equals the answer directly, with no subtraction from 1 needed. If you instead think of "1 minus probability of going off board," you would need to track cumulative off-board mass, which is more error-prone. The direct on-board summation is both simpler and numerically more stable.

Python (space-optimized): dirs = [(1,2),(1,-2),(-1,2),(-1,-2),(2,1),(2,-1),(-2,1),(-2,-1)]; prev = [[0.0]*n for _ in range(n)]; prev[row][col] = 1.0; for _ in range(k): curr = [[0.0]*n for _ in range(n)]; [curr[r+dr][c+dc].__add__(prev[r][c]/8) or setattr ... ]. In clean form: iterate all (r,c), all dirs, bounds-check, add prev[r][c]/8 to curr[r+dr][c+dc]. After k steps, return sum(sum(row) for row in prev). Time O(k·n²), space O(n²).

Java (space-optimized): double[][] prev = new double[n][n]; prev[row][col] = 1.0; int[][] dirs = {{1,2},{1,-2},{-1,2},{-1,-2},{2,1},{2,-1},{-2,1},{-2,-1}}; for (int s = 0; s < k; s++) { double[][] curr = new double[n][n]; for (int r=0; r<n; r++) for (int c=0; c<n; c++) if (prev[r][c] > 0) for (int[] d : dirs) { int nr=r+d[0], nc=c+d[1]; if (nr>=0&&nr<n&&nc>=0&&nc<n) curr[nr][nc] += prev[r][c]/8.0; } prev = curr; } double ans=0; for (double[] row:prev) for (double v:row) ans+=v; return ans;

Both implementations skip cells where prev[r][c] == 0 for a minor practical speedup (though asymptotic complexity is unchanged). The final answer is the sum of all values in the last prev array. Note that Java uses double (64-bit) arithmetic throughout — using float (32-bit) introduces rounding errors that accumulate over 100 steps and may cause wrong answers on judges that check to 5 decimal places.

Knight Probability in Chessboard (LeetCode 688) belongs to a family of probability DP problems on grids. Out of Boundary Paths (LeetCode 576) is the closest relative: instead of probability, it counts the number of paths that go out of bounds from a starting cell in exactly m moves on an m×n grid. The DP structure is identical — propagate counts forward through 4-directional moves — but Out of Boundary counts exits rather than on-board mass. Solving one makes the other straightforward.

Unique Paths (LeetCode 62) and Minimum Path Sum (LeetCode 64) are deterministic grid DP problems without probability, but share the same 2D rolling-array pattern. They build the grid intuition needed for Knight Probability. Triangle (LeetCode 120) similarly uses a rolling 1D array along a triangular grid. These problems form a natural learning sequence: deterministic grid DP first, then probability grid DP.

More advanced extensions include Knight's Tour (placing a knight to visit all cells exactly once — a Hamiltonian path problem, NP-hard in general) and Dice Roll Simulation (LeetCode 1223), which combines DP with constraint tracking over sequences. The probability DP pattern from LeetCode 688 — forward-propagating probability mass through valid transitions — appears in Soup Servings (LeetCode 808) and Random Walk problems. Mastering the forward-propagation model is the core transferable skill.