935.骑士拨号器

骑士拨号器

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

我们将拨号 pad 看成是一个 3 x 4 的网格。

给定的 n，返回我们能拨出的不同号码的总数。

示例 1:

输入：n = 1
输出：10

示例 2:

输入：n = 2
输出：20

提示:

• 1 <= n <= 5000

解析

使用动态规划，根据骑士的跳跃规则统计每一步能到达的号码数量。

var knightDialer = function (n) {
  const MOD = 10 ** 9 + 7;
  const jumps = [
    [4, 6],
    [6, 8],
    [7, 9],
    [4, 8],
    [0, 3, 9],
    [],
    [0, 1, 7],
    [2, 6],
    [1, 3],
    [2, 4]
  ];

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

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

  return dp.reduce((a, b) => (a + b) % MOD, 0);
};

时间复杂度 O(n)，空间复杂度 O(1)。