力扣题目 - 935. 骑士拨号器

题目

还需要你前往力扣官网查看详细的题目要求 地址

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

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

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

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

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

6.因为答案可能很大，所以输出答案 取模 1e9 + 7 (结果 % 1e9+7)

思路

• 这题的思路用 js动态规划来解决 js动态规划建议去看视频了解
• 先算出个个点位可以移动的位置 ,比如 0 可以移动到4和6。 1 可以移动到6和8.以此类推得到 validJump 这个二维数组
• 当n为1时, 可以移动0步 得到第一行,从0-9开始移动的最大不同号码为数组(也就是不移动) dp = [1,1,1,1,1,1,1,1,1] = new Array(10).fill(1)
• 当n为2时, 可以移动1步 得到第二行,从0-9开始移动得最大不同号码为数组 next = [2,2,2,2,3,0,3,2,2,2]
• 解析第二行(规律还不明显) next[0] = 2 第一步从0移动,可以到4和6, 那么next[0]也可以是 next[0] = dp[4]+dp[6]
• 这时你需要 dp = next
• 当n为3时, 可以移动2步 得到第三行,从0-9开始移动得最大不同号码为数组 next = [6,5,4,5,6,0,6,5,4,5]
• 解析第三行(这时规律出来) next[0]= 6 第一步从0移动,可以得到 4和6。那么在 4 时,剩下一步,不就和第二行 从4开始移动一样吗
  同理在 6 时,也和第二行从6开始移动一样 得到结果 next[0] = dp(4) + dp(6)
• next[j] = validJump[j].reduce(…省略)
• 简单来说除了第一行之外, 其余行的都由(上一行某些数字的相加) validJump[j].reduce((acc,curr)=>acc+dp(curr))

代码

//     0  1  2  3  4  5  6  7  8  9   这是0-9数字

// 0   1  1  1  1  1  1  1  1  1  1
// 1   2  2  2  2  3  0  3  2  2  2
// 2
// 3
// 4
// n-1
// 这是步数(n-1)
let validJump = [
    [4, 6],
    [6, 8],
    [7, 9],
    [4, 8],
    [0, 3, 9],
    [],
    [0, 1, 7],
    [2, 6],
    [1, 3],
    [2, 4],
  ];
  const MOD = 1e9 + 7;
  var knightDialer = function (n) {
    if (n < 0) return 0;
    if (n === 1) return 10;
    // 第一行
    let dp = new Array(10).fill(1);
    for (let i = 1; i < n; i++) {
      let next = [];
      for (let j = 0; j < 10; j++) {
        let res = validJump[j];
        next[j] =
          res.reduce((acc, curr) => {
            return acc + dp[curr];
          }, 0) % MOD;
      }
      dp = next;
    }
    return dp.reduce((a, b) => a + b) % MOD;
  };