# 935. 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`

0 -> 4, 6
1 -> 6, 8
2 -> 7, 9
3 -> 4, 8
4 -> 3, 9, 0
5 ->
6 -> 1, 7, 0
7 -> 2, 6
8 -> 1, 3
9 -> 4, 2

``````class Solution {
public:
int knightDialer(int N) {
int res = 0, M = 1e9 + 7;
vector<vector<int>> dp(N, vector<int>(10));
vector<vector<int>> path{{4, 6}, {6, 8}, {7, 9}, {4, 8}, {3, 9, 0}, {}, {1, 7, 0}, {2, 6}, {1, 9}, {4, 2}};
for (int i = 0; i < 10; ++i) dp[0][i] = 1;
for (int i = 1; i < N; ++i) {
for (int j = 0; j <= 9; ++j) {
for (int idx : path[j]) {
dp[i][j] = (dp[i][j] + dp[i - 1][idx]) % M;
}
}
}
for (int i = 0; i < 10; ++i) res = (res + dp.back()[i]) % M;
return res;
}
};
``````

``````class Solution {
public:
int knightDialer(int N) {
int res = 0, M = 1e9 + 7;
vector<vector<int>> memo(N + 1, vector<int>(10));
vector<vector<int>> path{{4, 6}, {6, 8}, {7, 9}, {4, 8}, {3, 9, 0}, {}, {1, 7, 0}, {2, 6}, {1, 9}, {4, 2}};
for (int i = 0; i < 10; ++i) {
res = (res + helper(N - 1, i, path, memo)) % M;
}
return res;
}
int helper(int n, int cur, vector<vector<int>>& path, vector<vector<int>>& memo) {
if (n == 0) return 1;
if (memo[n][cur] != 0) return memo[n][cur];
int res = 0, M = 1e9 + 7;
for (int idx : path[cur]) {
res = (res + helper(n - 1, idx, path, memo)) % M;
}
return memo[n][cur] = res;
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/935

Letter Combinations of a Phone Number

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

https://leetcode.com/problems/knight-dialer/discuss/189265/Concise-Java-DP-Solution

https://leetcode.com/problems/knight-dialer/discuss/189271/Java-Top-Down-Memo-DP-O(N)

https://leetcode.com/problems/knight-dialer/discuss/190787/How-to-solve-this-problem-explained-for-noobs!!!

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation