Dynamic Programming • Math

Probability DP

Calculate the expected value or probability of a specific outcome by transitioning fractional states over time or steps.

Try Interactive Simulator

Overview

Probability DP doesn't just store `true` or `false` (can we reach state X?), it stores `float` values: "What is the mathematical probability we reach state X?"

The Push DP Pattern

Instead of "Pull DP" where a cell asks its neighbors for values, Probability DP often uses "Push DP". A cell takes its probability `P` and pushes `P / branches` to its valid next states.

State Optimization

Because the probabilities at step `K` only depend on step `K-1`, we only need to keep two 2D grids in memory: `dp` and `nextDp`.

Leaking Probabilities

If a move goes off the board, that fraction of the probability is lost forever. The final answer is just the sum of all probabilities remaining on the board.

Move 0 / 2

1.000

0

Code Tracker

:::

1let dp = Array.from({length: n}, () => Array(n).fill(0));

2dp[r][c] = 1.0; // Start position

3

4for (let k = 1; k <= K; k++) {

5 let nextDp = Array.from({length: n}, () => Array(n).fill(0));

6 for (let i = 0; i < n; i++) {

7 for (let j = 0; j < n; j++) {

8 if (dp[i][j] > 0) {

9 for (let [di, dj] of moves) {

10 if (isValid(i + di, j + dj)) {

11 nextDp[i + di][j + dj] += dp[i][j] / 8.0;

12 }

13 }

14 }

15 }

16 }

17 dp = nextDp;

18}

Probability Dp

Probability Dp

Probability DP

Overview

The Push DP Pattern

State Optimization

Leaking Probabilities

Probability DP

Overview

The Push DP Pattern

State Optimization

Leaking Probabilities