活用動態規劃DP 特殊的騎士撥號器 Knight Dialer_Leetcode #935

Sam te Kiefte on Unsplash

題目敘述

題目會給定一組數字鍵盤，要求我們每次撥號的時候都走象棋的"馬"步，也就是日字型的走法，請問給定長度的n的數字撥號方式有幾種?

最後回傳答案之前，記得對10⁹ + 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