Dynamic Programming21 sections · 916 units
Open in Course

Knight Probability - Transition

Eight directions

From position (r,c)(r, c), the knight can move to 8 positions: (r±1,c±2)(r \pm 1, c \pm 2) and (r±2,c±1)(r \pm 2, c \pm 1). Each move is chosen with probability 1/81/8.

The formula to compute dp[r][c][k]: dp[r][c][k]=18(r,c)movesdp[r][c][k1]dp[r][c][k] = \frac{1}{8} \sum_{(r', c') \in moves} dp[r'][c'][k-1] But wait: what if (r,c)(r', c') is off the board? Then that move contributes 00 to the sum. The knight fell off, so the probability of staying on-board from that path is 00.