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, n-1)'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, 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).

Complexity Analysis

  • Time Complexity: .

  • Space Complexity: .


Analysis written by: @awice.