骑士拨号器 图解题解

骑士拨号器到底在数多少个号码

国际象棋的骑士（也就是「马」）站在电话键盘上，每步按「日」字跳——直走两格再垂直拐一格。键盘排着 0 到 9，左下右下角的 * 和 # 不能落。骑士从任意数字起步、共跳 n-1 步拼成长度 n 的号码，问能拨多少个不同号码，对 1e9+7 取模（保留余数防溢出）。

n=1 哪都不跳、各数字算一个是 10；n=2 是 20，n=3 是 46。要数的是号码个数。

把所有号码都跳一遍，为什么行不通

每步在当前数字的邻居里挑一个落脚，一路走到底就是一个号码，可每多跳一步分叉翻几倍，n 稍大路径数就指数爆炸、逐条枚举跑不完。好在只问个数、不看具体号码。既然子问题反复撞见，算一次存起来复用——这就是动态规划（DP，落在某数字、还剩几步的方案数与怎么跳来的无关，算一次存 dp[step][d] 复用）。

邻接表怎么来，dp[step][d] 又存什么

先搭地基：把每个数字「一步能跳到谁」列出来，就是邻接表（记录谁与谁相邻的表）。比如 1 只能到 6、8，4 能到 0、3、9，0 只能到 4、6；而中间的 5 一跳就出键盘、没有邻居，是孤岛。这张表还对称：1 能到 6，6 也跳回 1。

再定义 dp[step][d]：已按 step+1 个键、末位停在 d 的号码个数（跳了 step 步落在 d 的号码数）。step 从 0 数起，dp[0][d] 是长度 1。答案是最后一行各 d 的 dp 值相加，因为末位可任取。

落在 d 的方案，为什么把来源全加起来

填表就靠一条转移：要让末位停在 d，上一步必在能一步跳到 d 的数字上，把这些来源在上一行的方案数全加起来就是 dp[step][d]，即能跳到 d 的所有 prev 的 dp[step-1][prev] 之和。各来源不重不漏，每加一次对 1e9+7 取模防溢出。

拿 n=3 把三行表亲手填出来

第 0 步是长度 1 的号码，骑士哪都不跳、停哪都算一个，dp[0] 十格全是 1，求和 10，正是 n=1 的答案。

跳第 1 步逐格看来源：末位 0 从 4、6 来是 2，末位 4 由 0、3、9 来是 3，末位 5 谁都跳不到是 0。整行 [2,2,2,2,3,0,3,2,2,2]，求和 20，对上 n=2。

再跳第 2 步只改取上一行 step1 的值：末位 0 来自 4、6 是 3+3=6，末位 1 来自 6、8 是 5，末位 4 来自 0、3、9 是 6。整行 [6,5,4,5,6,0,6,5,4,5]，求和 46，与示例对上。

n=1 还跳了一步，答案为什么凭空翻倍

最容易踩的坑是循环次数：dp 初始化全 1 时号码已有 1 个数字，故只需再跳 n-1 步。n=1 一步都不该跳、答案是 dp[0] 求和的 10；多跑 1 步就把 10 错算成 20，正好翻倍。取模也别漏，否则大 n 撑爆整型。

复杂度上，数字只有 10 个、邻居数固定，每步常数工作，跳 n-1 步共 O(n)（大 O 记号，描述规模变大时操作数怎么涨）。每行只依赖上一行，用两个长 10 的数组轮换（滚动数组，只留最近几行覆盖旧值），空间 O(1)。

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;
    }
}