Welcome to Subscribe On Youtube

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;
    }
};
  • 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;
        }
    }
    
    ############
    
    class Solution {
        private static final int MOD = (int) 1e9 + 7;
    
        public int knightDialer(int n) {
            if (n == 1) {
                return 10;
            }
            long[] f = new long[10];
            Arrays.fill(f, 1);
            while (--n > 0) {
                long[] t = new long[10];
                t[0] = f[4] + f[6];
                t[1] = f[6] + f[8];
                t[2] = f[7] + f[9];
                t[3] = f[4] + f[8];
                t[4] = f[0] + f[3] + f[9];
                t[6] = f[0] + f[1] + f[7];
                t[7] = f[2] + f[6];
                t[8] = f[1] + f[3];
                t[9] = f[2] + f[4];
                for (int i = 0; i < 10; ++i) {
                    f[i] = t[i] % MOD;
                }
            }
            long ans = 0;
            for (long v : f) {
                ans = (ans + v) % MOD;
            }
            return (int) ans;
        }
    }
    
  • // 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;
        }
    };
    
  • class Solution:
        def knightDialer(self, n: int) -> int:
            if n == 1:
                return 10
            f = [1] * 10
            for _ in range(n - 1):
                t = [0] * 10
                t[0] = f[4] + f[6]
                t[1] = f[6] + f[8]
                t[2] = f[7] + f[9]
                t[3] = f[4] + f[8]
                t[4] = f[0] + f[3] + f[9]
                t[6] = f[0] + f[1] + f[7]
                t[7] = f[2] + f[6]
                t[8] = f[1] + f[3]
                t[9] = f[2] + f[4]
                f = t
            return sum(t) % (10**9 + 7)
    
    ############
    
    class Solution:
        def knightDialer(self, N):
            """
            :type N: int
            :rtype: int
            """
            self.ans = dict()
            self.ans[0] = 10
            board = [[1] * 3 for _ in range(4)]
            board[3][0] = board[3][3] = 0
            pre_dict = {(i, j) : self.prevMove(i, j) for i in range(4) for j in range(3)}
            for n in range(1, N):
                new_board = copy.deepcopy(board)
                for i in range(4):
                    for j in range(3):
                        cur_move = 0
                        for x, y in pre_dict[(i, j)]:
                            cur_move = (cur_move + board[x][y]) % (10 ** 9 + 7)
                        new_board[i][j] = cur_move
                board = new_board
            return sum([board[i][j] for i in range(4) for j in range(3)]) % (10 ** 9 + 7)
            
        def prevMove(self, i, j):
            if (i, j) == (3, 0) or (i, j) == (3, 2):
                return []
            directions = [(-2, 1), (-1, 2), (1, 2), (2, 1), (2, -1), (1, -2), (-1, -2), (-2, -1)]
            res = []
            for d in directions:
                x, y = i + d[0], j + d[1]
                if 0 <= x < 4 and 0 <= y < 3 and (x, y) != (3, 0) and (x, y) != (3, 2):
                    res.append((x, y))
            return res
    
  • func knightDialer(n int) int {
    	if n == 1 {
    		return 10
    	}
    	f := make([]int, 10)
    	for i := range f {
    		f[i] = 1
    	}
    	mod := int(1e9) + 7
    	for i := 1; i < n; i++ {
    		t := make([]int, 10)
    		t[0] = f[4] + f[6]
    		t[1] = f[6] + f[8]
    		t[2] = f[7] + f[9]
    		t[3] = f[4] + f[8]
    		t[4] = f[0] + f[3] + f[9]
    		t[6] = f[0] + f[1] + f[7]
    		t[7] = f[2] + f[6]
    		t[8] = f[1] + f[3]
    		t[9] = f[2] + f[4]
    		for j, v := range t {
    			f[j] = v % mod
    		}
    	}
    	ans := 0
    	for _, v := range f {
    		ans = (ans + v) % mod
    	}
    	return ans
    }
    

All Problems

All Solutions