0935. Knight Dialer =================== 题目信息 -------- :题号: 0935 :难度: Medium :主题: 电话键盘、骑士移动、序列计数 :原题: `LeetCode 0935 `_ :重点: 第一位可以是任意数字;之后每一位必须由国际象棋骑士的一次合法跳跃到达,统计长度恰为 ``n`` 的不同数字序列 题目重述 -------- 把数字 ``0`` 至 ``9`` 按普通电话键盘布局排列。一个棋子按照国际象棋骑士规则移动:每次在一个方向移动两格,再沿垂直方向移动一格;移动后必须仍落在某个数字键上。 可以从任意数字键开始,每按下当前数字后移动一次并按下新数字,直到得到恰好 ``n`` 位的数字序列。请返回所有可能序列的数量,并对 ``10^9 + 7`` 取模。不同起点或任一位置数字不同都视为不同序列。 ``1 <= n <= 5000``。 自建示例 -------- 连续执行两次骑士跳跃: .. code-block:: text 输入:n = 3 输出:46 解释:长度为 2 的 20 条有向跳跃继续各自扩展一跳后,共形成 46 个长度为 3 的合法数字序列。 序列只有一位: .. code-block:: text 输入:n = 1 输出:10 解释:不需要移动骑士,数字 0 至 9 都可以单独作为起点,因此共有 10 个序列。