A chess knight sits on a phone dial pad. You're given an integer n representing the number of hops. Starting from any digit ( through ), count how many distinct phone numbers of length n you can dial. The knight moves in an L-shape, just like in chess. Google frequently asks DP problems on grids and graphs. This one combines phone pad geometry with state transitions.
For n = 1, the answer is . Each single digit is a valid number. For n = 2, from digit the knight can jump to or , giving numbers 16 and 18.
How would you count all paths of length n without retracing every one of them?