Solution
Approach 1: Dynamic Programming
Intuition
Let f(start, n)
be the number of ways to dial an n
digit number, where the knight starts at square start
. We can create a recursion, writing this in terms of f(x, n1)
's.
Algorithm
By hand or otherwise, have a way to query what moves are available at each square. This implies the exact recursion for f
. For example, from 1
we can move to 6, 8
, so f(1, n) = f(6, n1) + f(8, n1)
.
After, let's keep track of dp[start] = f(start, n)
, and update it for each n from 1, 2, ..., N
.
At the end, the answer is f(0, N) + f(1, N) + ... + f(9, N) = sum(dp)
.
Complexity Analysis

Time Complexity: .

Space Complexity: .
Analysis written by: @awice.