LeetCode 935中等动态规划
骑士拨号器 图解题解
这道题到底在问什么
象棋骑士放在电话键盘的某个数字上，按骑士走「日」字的规则跳。骑士起步可放在任意数字上，一共跳 n-1 步（即按下 n 个数字）。问能拨出多少个不同的号码，结果对 1e9+7 取模。
- 输入
- n = 1 → 输出：10（光站着不跳，10 个数字各算一个）
- 输入
- n = 2 → 输出：20
- 输入
- n = 3 → 输出：46
最优解：一步一步想明白
- 34 行 3 列，含两个空角这是电话键盘：数字 0~9 排成这样。左下角和右下角是 * 和 #（这里画成「·」），骑士不能落在上面。
- 4走「日」字 = 两格直 + 一格拐象棋里马走「日」：往一个方向直走两格、再垂直拐一格。在键盘上，这决定了从某个数字一步能跳到哪几个数字——下面一个个看。
- 51 → {6, 8}骑士站在 1（橙色）。走「日」字，它只能跳到 6 和 8（橙黄高亮）。所以从 1 出发，下一个数字只有这两种选择。
- 64 → {0, 3, 9}换到 4，它能跳到 0、3、9 三个。位置不同，邻居数量也不同——这张「能跳到谁」的表是这题的地基。
- 76 → {0, 1, 7}6 能跳到 0、1、7。注意 1 能跳到 6、6 也能跳回 1——这种「跳跃关系」是双向对称的。
- 80 → {4, 6}底下的 0 只能跳到 4 和 6。0 位置偏，所以邻居少。
- 95 → {}（孤岛）中间的 5 很特殊：骑士从 5 走「日」字会跳出键盘，所以它没有任何邻居。一旦跳出，5 就只能当「起点的第一个数字」，之后再也回不来。
- 10邻接表 moves[d]把每个数字「一步能跳到谁」全列出来，就是这张邻接表。它对称：a 在 b 的列表里，b 也在 a 的列表里。有了它，剩下就是数路径。
- 11把所有路径一条条走出来最直白：从 10 个起点分别出发，每步在邻居里挑一个跳，把所有可能的路径都走一遍。n 大了路径会指数爆炸，太慢。
- 12不在乎具体路径，只数条数题目只问有多少个号码，不要具体号码。而「落在某数字、还要再跳几步」的方案数是固定的，与历史无关——这正是动态规划能省掉重复计算的根。
- 13dp[step][d] = 长度 step+1、末位是 d 的号码数我们换个角度：dp[step][d] 表示已经按了 step+1 个键、最后一个键是 d 的号码有多少个。求出最后一行全部加起来就是答案。
- 14从能跳到 d 的格汇总要落在 d，上一步必然站在某个「能跳到 d」的数字 prev 上。把这些 prev 的方案数全加起来，就是这一步落在 d 的方案数。下面用 n=3 把表填出来。
- 15dp[step][digit]这是要填的 DP 表：列是末位数字 0~9，行是跳的步数。step0 是号码长度 1，step2 是长度 3。一行填完再填下一行。
- 16长度 1：每个数字算 1 个号码第 0 步（号码长度 1）：骑士哪都不跳，停在任一数字都算一个号码，所以 dp[0][d] 全是 1。这一行加起来 = 10，正是 n=1 的答案。
- 17谁能跳到 0？ {4, 6}要让末位是 0，上一步得站在能跳到 0 的数字上：4 或 6。把它们 step0 的值加起来 1+1=2，填入 dp[1][0]。
- 18谁能跳到 1？ {6, 8}末位是 1：上一步在 6 或 8，加起来 = 2。dp[1][0] 已填好（灰）。一格一格往右推。
- 19谁能跳到 4？ {0, 3, 9}末位是 4：能跳到 4 的有三个数字 0、3、9，所以 dp[1][4] = 3。邻居多的格子，方案数就更大。2、3 也已填好（灰）。
- 20谁能跳到 5？ 没有！末位是 5：没有任何数字能跳到 5（它是孤岛），所以 dp[1][5] = 0。一旦跳了步，就再也停不到 5 了。
- 21其余数字同理填好把 6、7、8、9 也照样填好，step1 这行是 [2,2,2,2,3,0,3,2,2,2]。整行加起来 = 20，正好是 n=2 的答案。
- 22用 step1 的值再汇总一次进入第 2 步。规则不变——末位 0 来自 4 和 6，但这次取的是 step1 的值：3 + 3 = 6。每一步都建立在上一步之上。
- 23末位 1 来自 {6, 8}末位 1：来自 step1 的 6(=3) 和 8(=2)，加起来 = 5。dp[2][0] 已落定（灰）。
- 24末位 4 来自 {0, 3, 9}末位 4：来自 step1 的 0、3、9（都是 2），加起来 = 6。2、3 也按同法填好了（灰）。
- 25末位 6 来自 {0, 1, 7}末位 6：来自 step1 的 0、1、7（都是 2），加起来 = 6。中间的 5 仍是 0（灰），因为没人能跳到它。继续把剩下几格填完。
- 26长度 3 的号码按末位分组把 step2 这行全部填完：[6,5,4,5,6,0,6,5,4,5]。每个格子 = 长度 3、末位是该数字的号码个数。还差最后一步——把它们加起来。
- 27最后一行整行相加n=3 的答案 = step2 整行之和 = 6+5+4+5+6+0+6+5+4+5 = 46，和示例完全对上。最后一行求和就是最终答案，因为号码末位可以是任意数字。
- 28step 行只依赖 step-1 行每行只依赖紧挨着的上一行，更早的行用完就丢。所以空间能从「n×10」压到「两个长度 10 的数组」——这就是滚动数组优化。
- 31记住这一句凡是「求有多少种走法 / 多少条路径」的题，别傻乎乎一条条走。按「当前在哪、还剩几步」分组，把方案数累加，是这类计数 DP 的通用思路。
- 33n=1 却还跳了一步如果 n=1 还多跳了一步，就把答案从正确的 10（step0 之和）错算成 20。所以循环次数必须是 n-1，n=1 时一步都不跳。
⚠️ 容易写错的地方
✗ 错：忘了对 1e9+7 取模
✓ 对：每次累加后立刻取模
n 大时方案数爆炸，不取模会溢出，C++/Java 还要先用 long
✗ 错：把 5 当普通数字给它配邻居
✓ 对：moves[5] 是空表
骑士从 5 走日字会跳出键盘，5 没有任何可达邻居
✗ 错：循环跳了 n 步
✓ 对：只跳 n-1 步
step0 已是长度 1 的号码，再跳 n-1 次才凑满 n 个数字
完整代码（Python / C++ / Java）
Python
class Solution:
def knightDialer(self, n):
MOD = 10 ** 9 + 7
moves = [[4, 6], [6, 8], [7, 9], [4, 8], [0, 3, 9],
[], [0, 1, 7], [2, 6], [1, 3], [2, 4]]
dp = [1] * 10 # step0: 长度1 都是1
for _ in range(n - 1): # 再跳 n-1 步
ndp = [0] * 10
for d in range(10):
for nb in moves[d]: # d 能跳到 nb
ndp[nb] = (ndp[nb] + dp[d]) % MOD
dp = ndp
return sum(dp) % MOD # 最后一行求和C++
class Solution {
public:
int knightDialer(int n) {
const int MOD = 1e9 + 7;
vector<vector<int>> moves = {{4,6},{6,8},{7,9},{4,8},
{0,3,9},{},{0,1,7},{2,6},{1,3},{2,4}};
vector<long long> dp(10, 1); // step0
for (int s = 0; s < n - 1; s++) { // 跳 n-1 步
vector<long long> ndp(10, 0);
for (int d = 0; d < 10; d++)
for (int nb : moves[d]) // d -> nb
ndp[nb] = (ndp[nb] + dp[d]) % MOD;
dp = ndp;
}
long long ans = 0;
for (long long x : dp) ans = (ans + x) % MOD;
return (int)ans;
}
};Java
class Solution {
public int knightDialer(int n) {
final int MOD = 1000000007;
int[][] moves = {{4,6},{6,8},{7,9},{4,8},{0,3,9},
{}, {0,1,7}, {2,6}, {1,3}, {2,4}};
long[] dp = new long[10];
for (int d = 0; d < 10; d++) dp[d] = 1; // step0
for (int s = 0; s < n - 1; s++) { // 跳 n-1 步
long[] ndp = new long[10];
for (int d = 0; d < 10; d++) {
for (int nb : moves[d]) { // d -> nb
ndp[nb] = (ndp[nb] + dp[d]) % MOD;
}
}
dp = ndp;
}
long ans = 0;
for (long x : dp) ans = (ans + x) % MOD;
return (int) ans;
}
}复杂度
时间
O(n)
跳 n-1 步，每步处理 10 个数字 + 各自固定几个邻居，常数工作
空间
O(1)
邻接表固定 10 个数字，dp 只用两个长度 10 的数组滚动
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 骑士拨号器 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么用 DP 而不是直接 DFS 枚举所有号码？+
DFS 会把路径数指数级展开，n=5000 根本跑不完。DP 把「在某数字、还剩几步」的方案数缓存下来，不同前缀共享同一个子状态，复杂度降到 O(n)。
如果 n 大到 1e9 还能更快吗？+
能。转移是线性的，可写成 10×10 的转移矩阵，用矩阵快速幂把时间降到 O(10³·log n)。键盘大小固定，所以矩阵幂非常实用。
为什么必须取模、还要用 long？+
方案数随 n 指数增长，远超 int/long 范围。每步累加后对 1e9+7 取模把数值压在范围内；累加瞬间可能超 int，所以中间用 long 再取模。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 骑士拨号器 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。