0935. Knight Dialer

题目信息

题号:

0935

难度:

Medium

主题:

电话键盘、骑士移动、序列计数

原题:

LeetCode 0935

重点:

第一位可以是任意数字;之后每一位必须由国际象棋骑士的一次合法跳跃到达,统计长度恰为 n 的不同数字序列

题目重述

把数字 0 至 9 按普通电话键盘布局排列。一个棋子按照国际象棋骑士规则移动:每次在一个方向移动两格,再沿垂直方向移动一格;移动后必须仍落在某个数字键上。

可以从任意数字键开始,每按下当前数字后移动一次并按下新数字,直到得到恰好 n 位的数字序列。请返回所有可能序列的数量,并对 10^9 + 7 取模。不同起点或任一位置数字不同都视为不同序列。

1 <= n <= 5000。

自建示例

连续执行两次骑士跳跃:

输入:n = 3
输出:46
解释:长度为 2 的 20 条有向跳跃继续各自扩展一跳后,共形成 46 个长度为 3 的合法数字序列。

序列只有一位:

输入:n = 1
输出:10
解释:不需要移动骑士,数字 0 至 9 都可以单独作为起点,因此共有 10 个序列。