動態規劃DP: 計算有幾個母音直線排列 Count Vowels Permutation_Leetcode #1220

Jean-Louis Paulin on Unsplash

題目敘述

題目會給定一組規則，要求我們計算給定長度下的母音直線排列有幾種?

規則:

a 後面只能接e

e 後面只能接a 或 i

i 後面不能接 i (換句話說，接i之外的母音都可以)

o 後面只能接i 或 u

u 後面只能接a

最後回傳答案前，要求對10^9 + 7做除法取餘數。

詳細的題目可在這裡看到

測試範例

Example 1:

Input: n = 1
Output: 5
Explanation: All possible strings are: "a", "e", "i" , "o" and "u".

Example 2:

Input: n = 2
Output: 10
Explanation: All possible strings are: "ae", "ea", "ei", "ia", "ie", "io", "iu", "oi", "ou" and "ua".

Example 3: 

Input: n = 5
Output: 68

約束條件

Constraints:

• 1 <= n <= 2 * 10^4

演算法

依照轉換規則，推導出對應的狀態轉移遞迴關係式:

a 後面只能接e

e 後面只能接a 或 i

i 後面不能接 i (換句話說，接i之外的母音都可以)

o 後面只能接i 或 u

u 後面只能接a

=> 推導出

a 後面只能接e

e 後面只能接a 或 i

i 後面只能接a, 或 e, 或 o, 或 u

o 後面只能接i 或 u

u 後面只能接a

=> 推導出

a結尾的字串來自 前一個e結尾的字串, 前一個i結尾的字串, 前一個u結尾的字串

e結尾的字串來自 前一個a結尾的字串, 前一個i結尾的字串

i結尾的字串來自 前一個e結尾的字串, 前一個o結尾的字串

o結尾的字串來自 前一個i結尾的字串

u結尾的字串來自 前一個i結尾的字串, 前一個o結尾的字串

初始條件: 一開始長度為一的方法數各有一種，分別是

a, e, i, o, u 本身，對應到字串長度1,1,1,1,1

造一個迴圈，從長度為2開始往上更新每個母音結尾的直線排列數。

最後，回傳答案前，記得對10^9 + 7做除法取餘數。

程式碼

class Solution:
　def countVowelPermutation(self, n: int) -> int:
　　
　　modulo = 10**9 + 7
　　
　　# initialization for length of permutation = 1
　　(a, e, i, o, u) = (1, 1, 1, 1, 1)
　　
　　length_of_permutation = 2
　　while length_of_permutation <= n:
　　　
　　　# update total method count by transition rule
　　　end_with_a = e + i + u
　
　　　end_with_e = a + i

　　　end_with_i = e + o
　　   
　　　end_with_o = i
   
　　　end_with_u = i + o
			
						# update method count of ending with a e i o u
　　　(a, e, i, o, u) = (end_with_a, end_with_e, end_with_i, end_with_o, end_with_u )
　　　
　　
　　　length_of_permutation += 1
　　

　　return (a + e + i + o + u) % modulo

複雜度分析

時間複雜度:

O( n ) bottom-up 從 字串長度為1 開始遞迴更新到 字串長度為n。

空間複雜度:

O( 1 ) 使用到的都是臨時變數，所佔用記憶體空間為常數級別。

關鍵知識點

關鍵在於從題目給的字串規則，推導出每個母音結尾的遞迴狀態轉移關係式。

Reference:

[1] Python O(1) aux space by DP. 70%+ [w/ Comment] - Count Vowels Permutation - LeetCode