Formatted question description: https://leetcode.ca/all/935.html

935. Knight Dialer (Medium)

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

Solution 1. DP

// OJ: https://leetcode.com/problems/knight-dialer/

// Time: O(N)
// Space: O(1)
class Solution {
    vector<vector<int>> next { {4, 6}, {6, 8}, {7, 9}, {4, 8}, {0, 3, 9}, {}, {0, 1, 7}, {2, 6}, {1, 3}, {2, 4} };
public:
    int knightDialer(int N) {
        vector<vector<int>> dp(2, vector<int>(10, 1));
        int mod = 1e9 + 7, ans = 0;
        for (int i = 2; i <= N; ++i) {
            for (int j = 0; j <= 9; ++j) {
                dp[i % 2][j] = 0;
                for (int n : next[j]) {
                    dp[i % 2][j] = (dp[i % 2][j] + dp[(i - 1) % 2][n]) % mod;
                }
            }
        }
        for (int i = 0; i <= 9; ++i) ans = (ans + dp[N % 2][i]) % mod;
        return ans;
    }
};

Java

class Solution {
    public int knightDialer(int N) {
        final int MODULO = 1000000007;
        Map<Integer, int[]> adjacentMap = new HashMap<Integer, int[]>();
        adjacentMap.put(0, new int[]{4, 6});
        adjacentMap.put(1, new int[]{6, 8});
        adjacentMap.put(2, new int[]{7, 9});
        adjacentMap.put(3, new int[]{4, 8});
        adjacentMap.put(4, new int[]{0, 3, 9});
        adjacentMap.put(5, new int[0]);
        adjacentMap.put(6, new int[]{0, 1, 7});
        adjacentMap.put(7, new int[]{2, 6});
        adjacentMap.put(8, new int[]{1, 3});
        adjacentMap.put(9, new int[]{2, 4});
        int[][] dp = new int[N][10];
        for (int i = 0; i < 10; i++)
            dp[0][i] = 1;
        for (int i = 1; i < N; i++) {
            for (int j = 0; j < 10; j++) {
                int[] adjacents = adjacentMap.get(j);
                for (int adjacent : adjacents)
                    dp[i][j] = (dp[i][j] + dp[i - 1][adjacent]) % MODULO;
            }
        }
        int sum = 0;
        for (int i = 0; i < 10; i++)
            sum = (sum + dp[N - 1][i]) % MODULO;
        return sum;
    }
}

All Problems

All Solutions