力扣题目 - 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;};