0935. 骑士拨号器 #

标签：动态规划
难度：中等

题目大意 #

描述：象棋骑士可以垂直移动两个方格，水平移动一个方格，或者水平移动两个方格，垂直移动一个方格（两者都形成一个 $L$ 的形状），如下图所示。

现在我们有一个象棋其实和一个电话垫，如下图所示，骑士只能站在一个数字单元格上（$0 \sim 9$）。

现在给定一个整数 $n$。

要求：返回我们可以拨多少个长度为 $n$ 的不同电话号码。因为答案可能很大，所以最终答案需要对 $10^9 + 7$ 进行取模。

说明：

可以将骑士放在任何数字单元格上，然后执行 $n - 1$ 次移动来获得长度为 $n$ 的电话号码。
$1 \le n \le 5000$。

示例：

示例 1：

1
2
3


输入：n = 1
输出：10
解释：我们需要拨一个长度为1的数字，所以把骑士放在10个单元格中的任何一个数字单元格上都能满足条件。

示例 2：

1
2
3


输入：n = 2
输出：20
解释：我们可以拨打的所有有效号码为[04, 06, 16, 18, 27, 29, 34, 38, 40, 43, 49, 60, 61, 67, 72, 76, 81, 83, 92, 94]

解题思路 #

思路 1：动态规划 #

根据象棋骑士的跳跃规则，以及电话键盘的样式，我们可以预先处理一下象棋骑士当前位置与下一步能跳跃到的位置关系，将其存入哈希表中，方便查询。

接下来我们可以用动态规划的方式，计算出跳跃 $n - 1$ 次总共能得到多少个长度为 $n$ 的不同电话号码。

1. 划分阶段 #

按照步数、所处数字位置进行阶段划分。

2. 定义状态 #

定义状态 $dp[i][v]$ 表示为：第 $i$ 步到达键位 $u$ 总共能到的长度为 $i + 1$ 的不同电话号码个数。

3. 状态转移方程 #

第 $i$ 步到达键位 $v$ 所能得到的不同电话号码个数，取决于 $i - 1$ 步中所有能到达 $v$ 的键位 $u$ 的不同电话号码个数总和。

呢状态转移方程为：$dp[i][v] = \sum dp[i - 1][u]$（可以从 $u$ 跳到 $v$）。

4. 初始条件 #

第 $0$ 步（位于开始位置）所能得到的电话号码个数为 $1$，因为开始时可以将骑士放在任何数字单元格上，所以所有的 $dp[0][v] = 1$。

5. 最终结果 #

根据我们之前定义的状态，$dp[i][v]$ 表示为：第 $i$ 步到达键位 $u$ 总共能到的长度为 $i + 1$ 的不同电话号码个数。所以最终结果为第 $n - 1$ 行所有的 $dp[n - 1][v]$ 的总和。

思路 1：代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


class Solution:
    def knightDialer(self, n: int) -> int:
        graph = {
            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]
        }

        MOD = 10 ** 9 + 7
        dp = [[0 for _ in range(10)] for _ in range(n)]
        for v in range(10):
            dp[0][v] = 1

        for i in range(1, n):
            for u in range(10):
                for v in graph[u]:
                    dp[i][v] = (dp[i][v] + dp[i - 1][u]) % MOD
        
        return sum(dp[n - 1]) % MOD

思路 1：复杂度分析 #

时间复杂度：$O(n \times 10)$，其中 $n$ 为给定整数。
空间复杂度：$O(n \times 10)$。