The idea
A probability DP stores, for each state, the chance of being in it. Start with probability 1 in the initial state; each transition passes on its share: the state’s probability times the chance of that move.
Probabilities of outcomes that cannot happen together add up; those of independent steps multiply.
The answer is the total probability of the states you are asked about. For a piece moving at random on a board, the state is simply the square it stands on.
Sample problem
688. Knight Probability in Chessboard ↗ Medium
A knight starts on a square of an n × n board and makes exactly k moves, each chosen uniformly from the 8 knight moves, even if it leads off the board. Once off, it stays off. Return the probability that it is still on the board at the end.
n = 3, k = 2, row = 0, column = 0 output = 0.0625
Why the solution works
There are 8ᵏ move sequences, but two sequences that put the knight on the same square after the same number of moves have the same future. So track one number per square: the probability of standing on it.
Start with probability 1 on the starting square. Each move, every square sends one eighth of its probability to each of its 8 targets; shares that land outside the board are dropped.
After k moves, the probabilities remaining on the board add up to the answer, because standing on different squares are outcomes that cannot happen together.
Complexity: O(k · n² · 8) time, O(n²) memory.
Watch out
- Print enough digits:
setprecision(10)or%.10f. - When the set of possible moves depends on the state, so does the denominator.
- Do not compare doubles with
==.