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 }