題目

還需要你前往力扣官網查看詳細的題目要求 地址

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;};