##### 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[]>();
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++) {
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
}