Knight Probability - Walkthrough

A knight starts at $(r, c)$ on an $n \times n$ board. After $k$ moves, what's the probability it's still on the board? $dp[step][r][c]$ = probability of being at $(r, c)$ after $step$ moves, starting from the initial position.

Initial: $dp[0][r_0][c_0] = 1$. Transition: each cell distributes its probability equally to 8 knight-move destinations. After $k$ steps, sum all $dp[k][r][c]$ for valid $(r, c)$. Moves that go off-board contribute to the "off-board" probability.