A knight starts at position on an chessboard. It makes exactly moves, where each move is chosen uniformly at random from the 8 possible knight moves. The knight might move off the board.
Once off, it stays off. What's the probability that the knight remains on the board after all moves? Before reading on, think: what should dp track? What's the base case? How do transitions work?