骑士拨号器

标签: 动态规划

难度: Medium

象棋骑士有一个独特的移动方式，它可以垂直移动两个方格，水平移动一个方格，或者水平移动两个方格，垂直移动一个方格(两者都形成一个 L 的形状)。

象棋骑士可能的移动方式如下图所示:

我们有一个象棋骑士和一个电话垫，如下所示，骑士只能站在一个数字单元格上(即蓝色单元格)。

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

你可以将骑士放置在任何数字单元格上，然后你应该执行 n - 1 次移动来获得长度为 n 的号码。所有的跳跃应该是有效的骑士跳跃。

因为答案可能很大，所以输出答案模 10⁹ + 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

Submission

运行时间: 101 ms

内存: 0.0 MB

import numpy as np

class Solution:
    def knightDialer(self, n: int) -> int:
        mod = 10 ** 9 + 7
        if n == 1:
            return 10
        mat = np.matrix([[0, 0, 0, 0, 1, 0, 1, 0, 0, 0],
                       [0, 0, 0, 0, 0, 0, 1, 0, 1, 0],
                       [0, 0, 0, 0, 0, 0, 0, 1, 0, 1],
                       [0, 0, 0, 0, 1, 0, 0, 0, 1, 0],
                       [1, 0, 0, 1, 0, 0, 0, 0, 0, 1],
                       [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
                       [1, 1, 0, 0, 0, 0, 0, 1, 0, 0],
                       [0, 0, 1, 0, 0, 0, 1, 0, 0, 0],
                       [0, 1, 0, 1, 0, 0, 0, 0, 0, 0],
                       [0, 0, 1, 0, 1, 0, 0, 0, 0, 0]])
        res, n = 1, n - 1
        while n:
            if n % 2: res = res * mat % mod
            mat = mat * mat % mod
            n //= 2
        return int(np.sum(res)) % mod

Explain

该题解使用矩阵快速幂的方法来解决骑士拨号器问题。首先构建一个10x10的转移矩阵，矩阵中的每个元素 mat[i][j] 表示从数字 i 跳到数字 j 的合法性（1表示合法，0表示不合法）。然后利用矩阵快速幂算法，将转移矩阵mat的n-1次方与初始状态向量相乘，得到从各个起点跳n-1次后到达各个数字的方案数。最后将这些方案数相加并取模，就得到了最终答案。

时间复杂度: O(logn)

空间复杂度: O(1)

import numpy as np

class Solution:
    def knightDialer(self, n: int) -> int:
        mod = 10 ** 9 + 7
        if n == 1:
            return 10
        # 构建转移矩阵
        mat = np.matrix([[0, 0, 0, 0, 1, 0, 1, 0, 0, 0],
                       [0, 0, 0, 0, 0, 0, 1, 0, 1, 0],
                       [0, 0, 0, 0, 0, 0, 0, 1, 0, 1],
                       [0, 0, 0, 0, 1, 0, 0, 0, 1, 0],
                       [1, 0, 0, 1, 0, 0, 0, 0, 0, 1],
                       [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
                       [1, 1, 0, 0, 0, 0, 0, 1, 0, 0],
                       [0, 0, 1, 0, 0, 0, 1, 0, 0, 0],
                       [0, 1, 0, 1, 0, 0, 0, 0, 0, 0],
                       [0, 0, 1, 0, 1, 0, 0, 0, 0, 0]])
        res, n = 1, n - 1
        # 快速幂算法计算 mat^(n-1)
        while n:
            if n % 2: res = res * mat % mod
            mat = mat * mat % mod
            n //= 2
        # 计算最终结果
        return int(np.sum(res)) % mod

Explore

转移矩阵的构建基于骑士在电话拨号键盘上的跳跃规则，类似于国际象棋中骑士的移动方式（'L'形）。例如，从数字1出发，骑士可以跳到数字6和8，因此在转移矩阵中，mat[1][6]和mat[1][8]将被设置为1，而从1到其他数字的位置将被设置为0。每个数字的合法移动位置都以此方式确定，确保每个矩阵元素反映从一个数字到另一个数字是否为合法的骑士跳跃。

矩阵快速幂算法是用来高效计算矩阵的高次幂。在此题中，需要计算转移矩阵的(n-1)次幂。快速幂算法利用了幂的二进制表示，通过循环每次将指数减半，如果当前指数为奇数，则把结果乘以当前的基矩阵，基矩阵每次循环都与自身相乘（平方）。这种方法将时间复杂度从O(n)降低到O(log n)，显著提高了计算效率。

在矩阵快速幂的过程中进行模操作是为了防止计算过程中的整数溢出，并且确保结果保持在一个可控的数值范围内。给定的模数10**9 + 7是一个大质数，常用于编程竞赛中以避免结果过大。对每次矩阵相乘的结果取模，保证不会因为数值过大而出现计算错误或效率问题。

初始状态向量代表了每个数字作为起始点的初始条件。在本题中，如果n为1，则所有数字都可作为有效起始点，因此初始状态向量应为包含10个元素的向量，每个数字初始状态为1。在计算了转移矩阵的(n-1)次幂之后，这个向量将与转移矩阵的结果相乘，以得出每个数字作为起始点跳n步可达的位置数量。该部分在题解中没有具体实现，通常需要在计算完矩阵快速幂后，将结果矩阵与初始状态向量相乘，以得到最终的答案。