What is the Knight Dialer problem?

The Knight Dialer problem asks for the number of valid phone numbers a knight can dial on a standard phone pad, following specific movement rules of a knight in chess.

How do you solve the Knight Dialer problem using dynamic programming?

By treating each digit as a state and transitioning between states based on knight moves, you can use dynamic programming to compute the number of valid paths for any given length n.

Why do we use modular arithmetic in the Knight Dialer problem?

Modular arithmetic is used to prevent overflow and to keep results within the bounds required by the problem, typically modulo 10^9 + 7.

What is the time and space complexity of the Knight Dialer problem?

The time complexity is O(n) and the space complexity is O(1), as the solution uses a rolling DP array to compute the result efficiently.

What are common pitfalls in solving the Knight Dialer problem?

Common pitfalls include not using modular arithmetic correctly, not optimizing space complexity, and misunderstanding the knight's movement rules.

#935

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

骑士拨号器

象棋骑士有一个独特的移动方式，它可以垂直移动两个方格，水平移动一个方格，或者水平移动两个方格，垂直移动一个方格(两者都形成一个 L 的形状)。象棋骑士可能的移动方式如下图所示: 我们有一个象棋骑士和一个电话垫，如下所示，骑士只能站在一个数字单元格上 (即蓝色单元格)。给定一个整数 n，返回…

动态规划

题目描述

象棋骑士有一个独特的移动方式，它可以垂直移动两个方格，水平移动一个方格，或者水平移动两个方格，垂直移动一个方格(两者都形成一个 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

lightbulb

解题思路

方法一：递推

根据题目描述，我们需要计算出长度为 $n$ 的不同电话号码的数量。其中，每个数字的上一个数字只有固定的几个，我们可以列出每个数字的上一个数字：

当前数字	上一个数字
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

我们可以通过递推的方式，计算出长度为 $n$ 的不同电话号码的数量。设 $f[i]$ 表示长度为 $i$ 的不同电话号码的数量，初始时 $f[1] = 1$ 。对于长度为 $i$ 的电话号码，我们可以通过长度为 $i - 1$ 的电话号码计算出来，因此我们可以得到递推关系：

\begin{aligned} g[0] & = f[4] + f[6] \\ g[1] & = f[6] + f[8] \\ g[2] & = f[7] + f[9] \\ g[3] & = f[4] + f[8] \\ g[4] & = f[0] + f[3] + f[9] \\ g[6] & = f[0] + f[1] + f[7] \\ g[7] & = f[2] + f[6] \\ g[8] & = f[1] + f[3] \\ g[9] & = f[2] + f[4] \end{aligned}

然后，我们将 $f$ 更新为 $g$ ，继续计算下一个长度的电话号码，直到计算出长度为 $n$ 的电话号码的数量。

最后，我们将 $f$ 中所有元素相加，取模 $10^9 + 7$ ，即为答案。

时间复杂度 $O(n)$ ，其中 $n$ 为电话号码的长度。空间复杂度 $O(|\Sigma|)$ ，其中 $\Sigma$ 为数字集合，本题中 $|\Sigma| = 10$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

class Solution:
    def knightDialer(self, n: int) -> int:
        f = [1] * 10
        for _ in range(n - 1):
            g = [0] * 10
            g[0] = f[4] + f[6]
            g[1] = f[6] + f[8]
            g[2] = f[7] + f[9]
            g[3] = f[4] + f[8]
            g[4] = f[0] + f[3] + f[9]
            g[6] = f[0] + f[1] + f[7]
            g[7] = f[2] + f[6]
            g[8] = f[1] + f[3]
            g[9] = f[2] + f[4]
            f = g
        return sum(f) % (10**9 + 7)

speed

复杂度分析

指标	值
时间	complexity is O(n) due to the linear progression of the knight’s movements. Space complexity is reduced to O(1) by using only two arrays (current and previous states), optimizing memory usage while maintaining the same time efficiency.
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
The candidate should demonstrate an understanding of state transition dynamic programming for solving path problems.
question_mark
They should address space optimization through rolling arrays and modular arithmetic in large number problems.
question_mark
Look for clarity in their explanation of the knight’s movement rules and how they lead to state transitions in the dynamic programming solution.

warning

常见陷阱

外企场景

error
Not handling the modular arithmetic correctly, leading to overflow or incorrect results.
error
Failing to optimize space complexity, potentially using an O(n) space solution instead of the required O(1).
error
Misunderstanding the knight's movement rules, resulting in incorrect valid paths.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Consider different movement rules or additional constraints (e.g., limiting the knight to specific rows or columns).
arrow_right_alt
Modify the problem to ask for all the possible valid numbers rather than just the count.
arrow_right_alt
Increase the pad size or modify the grid structure to test for scalability of the solution.

help

常见问题

外企场景

继续练习

#931 下降路径最小和 #940 不同的子序列 II #943 最短超级串