題目敘述
題目會給定一組數字鍵盤，要求我們每次撥號的時候都走象棋的"馬"步，也就是日字型的走法，請問給定長度的n的數字撥號方式有幾種?
最後回傳答案之前，記得對109 + 7做除法取餘數。
詳細的題目可在這裡看到數字鍵盤的配置如下圖
在側邊欄中搜尋
象棋的"馬"步 日字型走法 示意圖
在側邊欄中搜尋
測試範例
Example 1:
Input: n = 1
Output: 10
Explanation: We need to dial a number of length 1, so placing the knight over any numeric cell of the 10 cells is sufficient.
Example 2:
Input: n = 2
Output: 20
Explanation: All the valid number we can dial are [04, 06, 16, 18, 27, 29, 34, 38, 40, 43, 49, 60, 61, 67, 72, 76, 81, 83, 92, 94]
Example 3:
Input: n = 3131
Output: 136006598
Explanation: Please take care of the mod.
約束條件
Constraints:
1 <= n <= 5000
演算法
其實和前面介紹過 計算有幾個母音直線排列 的那題很像，數字鍵盤定義域和值域都是固定的，可以先找出狀態轉移的State transfer diagram。再從狀態機的State transfer diagram實作出bottom-up的DP解法。
從數字鍵盤的位置和撥號規則(走馬步)找出規律
現在狀態，前一個狀態:
現在的0可以由前一步的4, 6走過來
現在的1可以由前一步的6, 8走過來
現在的2可以由前一步的7, 9走過來
現在的3可以由前一步的4, 8走過來
現在的4可以由前一步的0, 3, 9走過來
現在的5 無法由其他數字走過來 (實作上的細節，請留意)
現在的6可以由前一步的0, 1, 7走過來
現在的7可以由前一步的2, 6走過來
現在的8可以由前一步的1, 3走過來
現在的9可以由前一步的2, 4走過來
有了這些狀態轉移關係式後，就可以用迴圈，每次迭代更新數字鍵盤撥號的方法總數。
程式碼
class Solution:
def knightDialer(self, N):
'''
State Transfer function
Cur state comes from previous state
0 <-> 4, 6
1 <-> 6, 8
2 <-> 7, 9
3 <-> 4, 8
4 <-> 0, 3, 9
5 <-> NULL (i.e. No solution when length >= 2 )
6 <-> 0, 1, 7
7 <-> 2, 6
8 <-> 1, 3
9 <-> 2, 4
'''
CONSTANT = 10**9+7
method_count = [1 for _ in range(10)]
for step in range(N-1):
prev = method_count.copy()
method_count[0] = prev[4] + prev[6]
method_count[1] = prev[6] + prev[8]
method_count[2] = prev[7] + prev[9]
method_count[3] = prev[4] + prev[8]
method_count[4] = prev[0] + prev[3] + prev[9]
method_count[5] = 0 # NULL
method_count[6] = prev[0] + prev[1] + prev[7]
method_count[7] = prev[2] + prev[6]
method_count[8] = prev[1] + prev[3]
method_count[9] = prev[2] + prev[4]
return sum(method_count) % CONSTANT
複雜度分析
時間複雜度:
O( n ) bottom-up 從 撥號長度為1 開始遞迴更新到 撥號長度為n。
空間複雜度:
O( 1 ) 使用到的是固定大小，長度為10的暫存陣列 prev。
關鍵知識點
關鍵在於從題目給的數字鍵盤的位置 和 走馬步撥號的規則，推導出每個長度的撥號遞迴狀態轉移關係式。
這一題和前面介紹過 計算有幾個母音直線排列 的那題很像，強烈建議一起複習有限狀態及FSM結合DP動態規劃的解題觀念。
Reference:
[1] Python O(n) by Finite State Machine [w/ Visualization] - Knight Dialer - LeetCode
