Knight Dialer - A Classic Dynamic Programming Problem

This was a very interesting problem, and a classic application of Dynamic Programming. Here is the problem: https://leetcode.com/problems/knight-dialer/

A chess knight can move as indicated in the chess diagram below:

This time, we place our chess knight on any numbered key of a phone pad (indicated above), and the knight makes N-1 hops.  Each hop must be from one key to another numbered key.

Each time it lands on a key (including the initial placement of the knight), it presses the number of that key, pressing N digits total.

How many distinct numbers can you dial in this manner?

Since the answer may be large, output the answer modulo 10^9 + 7.

Example 1:

Input: 1

Output: 10

Example 2:

Input: 2

Output: 20

Example 3:

Input: 3

Output: 46

Note:

• 1 <= N <= 5000

The 10^9 + 7 to me is always the strongest indication that the solution should be done via DP. The also indication is that the N is very large (5000), hence if we try all the possibilities, we’re possibly talking about 9^5000, which is not tractable.

The way to think about the solution for this problem is the following: suppose that you have the solution for N-1. You know for each cell from 0..9 the solution for N-1 hops. In this case how can you get the solution for N hops? Well, what you can do is that for each cell, say cell(0), how many possibilities can you have? The number of possibilities for cell(0) is whatever the N-1 solution is for cell(4) plus whatever the N-1 solution is for cell(6). Once you do that for all cells, then you add them all up and you have the solution for N.

With that in mind, we build the solution by construction. The very first thing to do is to create a map mapping each cell to the corresponding cells based on how the knight moves (as I said above, for example, 0 maps to 4 and 6). That’s where you use the information about how the knight moves. Then you construct the solution for N=1 (trivial, no hops). From that point one, build the solution for 2…N. I use a hash table just because I find it super easy to manipulate the data structure.

Looking at the space complexity, it is a constant space. Time would be linear: N (max: 5000) * 10 (fixed) * 3 (max number of mapped cells).

Code is down below – cheers!!! ACC.

public class Solution
{
    public int KnightDialer(int N)
    {
        Hashtable map = new Hashtable();

        map.Add(0, new int[] { 4, 6, });
        map.Add(1, new int[] { 6, 8 });
        map.Add(2, new int[] { 7, 9 });
        map.Add(3, new int[] { 4, 8 });
        map.Add(4, new int[] { 0, 3, 9 });
        map.Add(5, new int[] { });
        map.Add(6, new int[] { 0, 1, 7 });
        map.Add(7, new int[] { 2, 6 });
        map.Add(8, new int[] { 1, 3 });
        map.Add(9, new int[] { 2, 4 });

        //DP
        Hashtable previous = new Hashtable();
        Hashtable current = new Hashtable();

        //N=1
        for (int i = 0; i < 10; i++)
        {
            previous.Add(i, 1);
        }
        current = (Hashtable)previous.Clone();

        //N>1
        for (int i = 1; i < N; i++)
        {
            current = new Hashtable();
            for (int j = 0; j < 10; j++)
            {
                current.Add(j, 0);
                int[] mapArray = (int[])map[j];
                for (int z = 0; z < mapArray.Length; z++)
                {
                    current[j] = ((int)current[j] + (int)previous[mapArray[z]]) % (1000000000 + 7);
                }
            }

            previous = (Hashtable)current.Clone();
        }

        int sum = 0;
        for (int i = 0; i < 10; i++)
        {
            sum = (sum + (int)current[i]) % (1000000000 + 7);
        }

        return sum;
    }
}