Medium

题目描述

国际象棋中的骑士有独特的移动方式，它可以垂直移动两个方格并水平移动一个方格，或者水平移动两个方格并垂直移动一个方格（两种移动都形成L形）。

我们有一个国际象棋骑士和一个电话拨号盘，如下所示，骑士只能站在数字单元格上（即蓝色单元格）。

1 2 3
4 5 6
7 8 9
  0

给定一个整数 n，返回我们可以拨打的长度为 n 的不同电话号码的数量。

你可以将骑士放在任何数字单元格上作为起始位置，然后你需要执行 n - 1 次跳跃来拨打长度为 n 的号码。所有跳跃都必须是有效的骑士跳跃。

由于答案可能非常大，请返回答案模 10^9 + 7 的结果。

示例 1:

输入: n = 1
输出: 10
解释: 我们需要拨打长度为1的号码，所以将骑士放在10个单元格中的任何一个都足够了。

示例 2:

输入: n = 2
输出: 20
解释: 所有有效的号码是 [04, 06, 16, 18, 27, 29, 34, 38, 40, 43, 49, 60, 61, 67, 72, 76, 81, 83, 92, 94]

示例 3:

输入: n = 3131
输出: 136006598
解释: 请注意取模。

约束条件:

  • 1 <= n <= 5000

解题思路

这是一道经典的动态规划问题。我们需要分析骑士在电话拨号盘上的移动规律。

首先，我们需要建立数字键盘的布局映射关系。观察电话拨号盘：

1 2 3
4 5 6
7 8 9
  0

根据骑士的移动规则（L形移动），我们可以构建每个数字能够到达的相邻数字列表：

  • 0 → [4, 6]
  • 1 → [6, 8]
  • 2 → [7, 9]
  • 3 → [4, 8]
  • 4 → [0, 3, 9]
  • 5 → [] (无法到达任何位置)
  • 6 → [0, 1, 7]
  • 7 → [2, 6]
  • 8 → [1, 3]
  • 9 → [2, 4]

动态规划思路： 定义 dp[i][j] 表示经过 i 步跳跃后，骑士位于数字 j 上的方案数。

状态转移方程：dp[i][j] = sum(dp[i-1][k]), 其中 k 是能够一步到达 j 的所有数字。

初始状态：dp[0][j] = 1 (对所有数字 j)，表示第一步可以选择任意数字。

最终答案是 sum(dp[n-1][j]) 对所有 j 的总和。

为了优化空间复杂度，我们可以使用滚动数组，只保存当前步和前一步的状态。

代码实现

class Solution {
public:
    int knightDialer(int n) {
        const int MOD = 1000000007;
        
        // 每个数字能够到达的下一个数字
        vector<vector<int>> moves = {
            {4, 6},       // 0
            {6, 8},       // 1
            {7, 9},       // 2
            {4, 8},       // 3
            {0, 3, 9},    // 4
            {},           // 5
            {0, 1, 7},    // 6
            {2, 6},       // 7
            {1, 3},       // 8
            {2, 4}        // 9
        };
        
        // 当前状态：每个数字位置的方案数
        vector<long long> prev(10, 1);
        
        for (int step = 1; step < n; step++) {
            vector<long long> curr(10, 0);
            
            for (int digit = 0; digit <= 9; digit++) {
                for (int next : moves[digit]) {
                    curr[next] = (curr[next] + prev[digit]) % MOD;
                }
            }
            
            prev = curr;
        }
        
        long long result = 0;
        for (int i = 0; i <= 9; i++) {
            result = (result + prev[i]) % MOD;
        }
        
        return result;
    }
};

class Solution:
    def knightDialer(self, n: int) -> int:
        MOD = 10**9 + 7
        
        # 每个数字能够到达的下一个数字
        moves = {
            0: [4, 6],
            1: [6, 8],
            2: [7, 9],
            3: [4, 8],
            4: [0, 3, 9],
            5: [],
            6: [0, 1, 7],
            7: [2, 6],
            8: [1, 3],
            9: [2, 4]
        }
        
        # 当前状态：每个数字位置的方案数
        prev = [1] * 10
        
        for step in range(1, n):
            curr = [0] * 10
            
            for digit in range(10):
                for next_digit in moves[digit]:
                    curr[next_digit] = (curr[next_digit] + prev[digit]) % MOD
            
            prev = curr
        
        return sum(prev) % MOD

public class Solution {
    public int KnightDialer(int n) {
        const int MOD = 1000000007;
        
        // 每个数字能够到达的下一个数字
        int[][] moves = new int[][] {
            new int[] {4, 6},       // 0
            new int[] {6, 8},       // 1
            new int[] {7, 9},       // 2
            new int[] {4, 8},       // 3
            new int[] {0, 3, 9},    // 4
            new int[] {},           // 5
            new int[] {0, 1, 7},    // 6
            new int[] {2, 6},       // 7
            new int[] {1, 3},       // 8
            new int[] {2, 4}        // 9
        };
        
        // 当前状态：每个数字位置的方案数
        long[] prev = new long[10];
        Array.Fill(prev, 1);
        
        for (int step = 1; step < n; step++) {
            long[] curr = new long[10];
            
            for (int digit = 0; digit <= 9; digit++) {
                foreach (int next in moves[digit]) {
                    curr[next] = (curr[next] + prev[digit]) % MOD;
                }
            }
            
            prev = curr;
        }
        
        long result = 0;
        for (int i = 0; i <= 9; i++) {
            result = (result + prev[i]) % MOD;
        }
        
        return (int)result;
    }
}

var knightDialer = function(n) {
    const MOD = 1000000007;
    
    // 每个数字能够到达的下一个数字
    const moves = {
        0: [4, 6],
        1: [6, 8],
        2: [7, 9],
        3: [4, 8],
        4: [0, 3, 9],
        5: [],
        6: [0, 1, 7],
        7: [2, 6],
        8: [1, 3],
        9: [2, 4]
    };
    
    // 当前状态：每个数字位置的方案数
    let prev = new Array(10).fill(1);
    
    for (let step = 1; step < n; step++) {
        const curr = new Array(10).fill(0);
        
        for (let digit = 0; digit <= 9; digit++) {
            for (const next of moves[digit]) {
                curr[next] = (curr[next] + prev[digit]) % MOD;
            }
        }
        
        prev = curr;
    }
    
    return prev.reduce((sum, count) => (sum + count) % MOD, 0);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n) - 需要进行 n-1 轮状态转移，每轮遍历10个数字及其邻接关系
空间复杂度O(1) - 只使用了固定大小的数组存储状态，与输入规模无关