骑士拨号器

先看清这块电话键盘：这是电话键盘：数字 0~9 排成这样。左下角和右下角是 * 和 #（这里画成「·」），骑士不能落在上面。

骑士怎么走：象棋里马走「日」：往一个方向直走两格、再垂直拐一格。在键盘上，这决定了从某个数字一步能跳到哪几个数字——下面一个个看。

从 1 出发能跳到哪：骑士站在 1（橙色）。走「日」字，它只能跳到 6 和 8（橙黄高亮）。所以从 1 出发，下一个数字只有这两种选择。

从 4 出发能跳到哪：换到 4，它能跳到 0、3、9 三个。位置不同，邻居数量也不同——这张「能跳到谁」的表是这题的地基。

从 6 出发能跳到哪：6 能跳到 0、1、7。注意 1 能跳到 6、6 也能跳回 1——这种「跳跃关系」是双向对称的。

从 0 出发能跳到哪：底下的 0 只能跳到 4 和 6。0 位置偏，所以邻居少。

特殊的 5 · 哪都跳不了：中间的 5 很特殊：骑士从 5 走「日」字会跳出键盘，所以它没有任何邻居。一旦跳出，5 就只能当「起点的第一个数字」，之后再也回不来。

把跳跃关系记成一张表：把每个数字「一步能跳到谁」全列出来，就是这张邻接表。它对称：a 在 b 的列表里，b 也在 a 的列表里。有了它，剩下就是数路径。

先想最直白的办法：最直白：从 10 个起点分别出发，每步在邻居里挑一个跳，把所有可能的路径都走一遍。n 大了路径会指数爆炸，太慢。

关键观察 · 数量可以累加：题目只问有多少个号码，不要具体号码。而「落在某数字、还要再跳几步」的方案数是固定的，与历史无关——这正是动态规划能省掉重复计算的根。

定义 DP 状态：我们换个角度：dp[step][d] 表示已经按了 step+1 个键、最后一个键是 d 的号码有多少个。求出最后一行全部加起来就是答案。

转移方程：要落在 d，上一步必然站在某个「能跳到 d」的数字 prev 上。把这些 prev 的方案数全加起来，就是这一步落在 d 的方案数。下面用 n=3 把表填出来。

建表 · 行=步，列=末位数字：这是要填的 DP 表：列是末位数字 0~9，行是跳的步数。step0 是号码长度 1，step2 是长度 3。一行填完再填下一行。

地基 · step0 全填 1：第 0 步（号码长度 1）：骑士哪都不跳，停在任一数字都算一个号码，所以 dp[0][d] 全是 1。这一行加起来 = 10，正是 n=1 的答案。

填 step1 · 落在 0：要让末位是 0，上一步得站在能跳到 0 的数字上：4 或 6。把它们 step0 的值加起来 1+1=2，填入 dp[1][0]。

填 step1 · 落在 1：末位是 1：上一步在 6 或 8，加起来 = 2。dp[1][0] 已填好（灰）。一格一格往右推。

填 step1 · 落在 4（邻居更多）：末位是 4：能跳到 4 的有三个数字 0、3、9，所以 dp[1][4] = 3。邻居多的格子，方案数就更大。2、3 也已填好（灰）。

填 step1 · 落在 5：末位是 5：没有任何数字能跳到 5（它是孤岛），所以 dp[1][5] = 0。一旦跳了步，就再也停不到 5 了。

填完 step1 · 整行：把 6、7、8、9 也照样填好，step1 这行是 [2,2,2,2,3,0,3,2,2,2]。整行加起来 = 20，正好是 n=2 的答案。

填 step2 · 落在 0：进入第 2 步。规则不变——末位 0 来自 4 和 6，但这次取的是 step1 的值：3 + 3 = 6。每一步都建立在上一步之上。

填 step2 · 落在 1：末位 1：来自 step1 的 6(=3) 和 8(=2)，加起来 = 5。dp[2][0] 已落定（灰）。

填 step2 · 落在 4：末位 4：来自 step1 的 0、3、9（都是 2），加起来 = 6。2、3 也按同法填好了（灰）。

填 step2 · 落在 6：末位 6：来自 step1 的 0、1、7（都是 2），加起来 = 6。中间的 5 仍是 0（灰），因为没人能跳到它。继续把剩下几格填完。

填完 step2 · 整行：把 step2 这行全部填完：[6,5,4,5,6,0,6,5,4,5]。每个格子 = 长度 3、末位是该数字的号码个数。还差最后一步——把它们加起来。

求和 · 得到答案：n=3 的答案 = step2 整行之和 = 6+5+4+5+6+0+6+5+4+5 = 46，和示例完全对上。最后一行求和就是最终答案，因为号码末位可以是任意数字。

滚动优化 · 只留两行：每行只依赖紧挨着的上一行，更早的行用完就丢。所以空间能从「n×10」压到「两个长度 10 的数组」——这就是滚动数组优化。

本质金句：凡是「求有多少种走法 / 多少条路径」的题，别傻乎乎一条条走。按「当前在哪、还剩几步」分组，把方案数累加，是这类计数 DP 的通用思路。

易错实演 · 多跳一步会怎样：如果 n=1 还多跳了一步，就把答案从正确的 10（step0 之和）错算成 20。所以循环次数必须是 n-1，n=1 时一步都不跳。

边界三连：n=1 是最容易写错的边界——很多人循环跳了 1 步导致答案翻倍。n 很大时只要每步取模就稳，时间仍是线性。

面试追问：把「DFS 为何超时、DP 如何省、n 极大时矩阵快速幂」这条线讲清楚，能体现你对计数 DP 与优化阶梯的完整理解。