# 0935. 騎士撥號器 ## 題目地址 (935. 騎士撥號器） <https://leetcode-cn.com/problems/knight-dialer/> ## 題目描述 ``` <pre class="calibre18">``` 國際象棋中的騎士可以按下圖所示進行移動： ``` ```  ``` <pre class="calibre18">``` 這一次，我們將 “騎士” 放在電話撥號盤的任意數字鍵（如上圖所示）上，接下來，騎士將會跳 N-1 步。每一步必須是從一個數字鍵跳到另一個數字鍵。 每當它落在一個鍵上（包括騎士的初始位置），都會撥出鍵所對應的數字，總共按下 N 位數字。 你能用這種方式撥出多少個不同的號碼？ 因為答案可能很大，所以輸出答案模 10^9 + 7。 示例 1： 輸入：1 輸出：10 示例 2： 輸入：2 輸出：20 示例 3： 輸入：3 輸出：46 提示： 1 <= N <= 5000 ``` ``` ## 前置知識 - DFS - 記憶化搜索 ## 深度優先遍歷（DFS） ## 公司 - 暫無 ### 思路 這道題要求解一個數字。并且每一個格子能夠跳的狀態是確定的。 因此我們的思路就是“狀態機”（動態規劃），暴力遍歷（BFS or DFS），這里我們使用 DFS。（注意這幾種思路并無本質不同） 對于每一個號碼鍵盤，我們可以轉移的狀態是確定的，我們做一個”預處理“，將這些狀態轉移記錄到一個數組 jump，其中 jump\[i\] 表示 i 位置可以跳的點（用一個數組來表示）。問題轉化為： - 從 0 開始所有的路徑 - 從 1 開始所有的路徑 - 從 2 開始所有的路徑 - ... - 從 9 開始所有的路徑 不管從幾開始思路都是一樣的。 我們使用一個函數 f(i, n) 表示`騎士在 i 的位置，還剩下 N 步可以走`的時候可以撥出的總的號碼數。那么問題就是求解 `f(0, N) + f(1, N) + f(2, N) + ... + f(9, N)`。對于 f(i, n)，我們初始化 cnt 為 0，由于 i 能跳的格子是 jump\[i\]，我們將其 `cnt += f(j, n - 1)`，其中 j 屬于 jump\[i\]，最終返回 cnt 即可。 不難看出，這種算法有大量重復計算，我們使用記憶化遞歸形式來減少重復計算。 這種算法勉強通過。 ### 代碼 ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">knightDialer</span><span class="hljs-params">(self, N: int)</span> -> int:</span> cnt = <span class="hljs-params">0</span> jump = [[<span class="hljs-params">4</span>, <span class="hljs-params">6</span>], [<span class="hljs-params">6</span>, <span class="hljs-params">8</span>], [<span class="hljs-params">7</span>, <span class="hljs-params">9</span>], [<span class="hljs-params">4</span>, <span class="hljs-params">8</span>], [ <span class="hljs-params">0</span>, <span class="hljs-params">3</span>, <span class="hljs-params">9</span>], [], [<span class="hljs-params">0</span>, <span class="hljs-params">1</span>, <span class="hljs-params">7</span>], [<span class="hljs-params">2</span>, <span class="hljs-params">6</span>], [<span class="hljs-params">1</span>, <span class="hljs-params">3</span>], [<span class="hljs-params">2</span>, <span class="hljs-params">4</span>]] visited = dict() <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">helper</span><span class="hljs-params">(i, n)</span>:</span> <span class="hljs-keyword">if</span> (i, n) <span class="hljs-keyword">in</span> visited: <span class="hljs-keyword">return</span> visited[(i, n)] <span class="hljs-keyword">if</span> n == <span class="hljs-params">1</span>: <span class="hljs-keyword">return</span> <span class="hljs-params">1</span> cnt = <span class="hljs-params">0</span> <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> jump[i]: cnt += helper(j, n - <span class="hljs-params">1</span>) visited[(i, n)] = cnt <span class="hljs-keyword">return</span> cnt <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-params">10</span>): cnt += helper(i, N) <span class="hljs-keyword">return</span> cnt % (<span class="hljs-params">10</span>**<span class="hljs-params">9</span> + <span class="hljs-params">7</span>) ``` ``` **復雜度分析** - 時間復雜度：O(N)O(N)O(N) - 空間復雜度：O(N)O(N)O(N) ## 樸素遍歷 ### 思路 我們使用迭代的形式來優化上述過程。我們初始化十個變量分別表示鍵盤不同位置能夠撥出的號碼數，并且初始化為 1。接下來我們只要循環 N - 1 次，不斷更新狀態即可。不過這種算法和上述算法并無本質不同。 ### 代碼 ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">knightDialer</span><span class="hljs-params">(self, N: int)</span> -> int:</span> a0 = a1 = a2 = a3 = a4 = a5 = a6 = a7 = a8 = a9 = <span class="hljs-params">1</span> <span class="hljs-keyword">for</span> _ <span class="hljs-keyword">in</span> range(N - <span class="hljs-params">1</span>): a0, a1, a2, a3, a4, a5, a6, a7, a8, a9 = a4 + a6, a6 + a8, a7 + \ a9, a4 + a8, a0 + a3 + a9, <span class="hljs-params">0</span>, a0 + a1 + a7, a2 + a6, a1 + a3, a2 + a4 <span class="hljs-keyword">return</span> (a0 + a1 + a2 + a3 + a4 + a5 + a6 + a7 + a8 + a9) % (<span class="hljs-params">10</span>**<span class="hljs-params">9</span> + <span class="hljs-params">7</span>) ``` ``` **復雜度分析** - 時間復雜度：O(N)O(N)O(N) - 空間復雜度：O(1)O(1)O(1) 歡迎關注我的公眾號《腦洞前端》獲取更多更新鮮的 LeetCode 題解