Approach 1: Dynamic Programming
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
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, n-1) + f(8, n-1).
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).
Time Complexity: .
Space Complexity: .
Analysis written by: @awice.