0935. 骑士拨号器【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 动态规划

1. 📝 题目描述

• leetcode

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

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

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

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

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

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

2. 🎯 s.1 - 动态规划

js] <<< ./solutions/1/1.c [c] <<< ./solutions/1/1.py [py

/**
 * @param {number} n
 * @return {number}
 */
var knightDialer = function (n) {
  const MOD = 1e9 + 7
  const moves = [
    [4, 6], // 0
    [6, 8], // 1
    [7, 9], // 2
    [4, 8], // 3
    [0, 3, 9], // 4
    [], // 5
    [0, 1, 7], // 6
    [2, 6], // 7
    [1, 3], // 8
    [2, 4], // 9
  ]

  let dp = new Array(10).fill(1)

  for (let step = 1; step < n; step++) {
    const next = new Array(10).fill(0)
    for (let i = 0; i < 10; i++) {
      for (const j of moves[i]) {
        next[i] = (next[i] + dp[j]) % MOD
      }
    }
    dp = next
  }

  let res = 0
  for (const x of dp) res = (res + x) % MOD
  return res
}

• 时间复杂度：$O(n)$，每步遍历 10 个数字和固定的跳转关系
• 空间复杂度：$O(1)$，只使用固定大小的 DP 数组

算法思路：

• 预定义每个数字键的骑士可达数字列表
• dp[i] 表示当前步以数字 i 结尾的方案数，初始全为 1
• 每步更新：$d{p}^{\prime }[i]=\sum dp[j]$，其中 j 是所有能跳到 i 的数字
• 最终答案为所有 dp[i] 之和