解題說明
Count Vowels Permutation
題目描述:
給定整數 n,計算長度為 n 的字串中,由母音字母 (a, e, i, o, u) 組成且滿足以下規則的排列數量(結果取模 10^9+7):
- a 後面只能接 e
- e 後面只能接 a 或 i
- i 後面不能接 i
- o 後面只能接 i 或 u
- u 後面只能接 a
解題思路:
這是一道典型的動態規劃(DP)問題。定義 dp[c] 為以字元 c 結尾的合法字串數量。根據規則,反推每個字元可以由哪些字元接過來:
- 以 a 結尾:前一個可以是 e, i, u
- 以 e 結尾:前一個可以是 a, i
- 以 i 結尾:前一個可以是 e, o
- 以 o 結尾:前一個可以是 i
- 以 u 結尾:前一個可以是 i, o
初始化長度 1 時每個字元的計數為 1,然後迭代 n-1 次,每次根據轉移規則更新。最後將五個字元的計數加總即為答案。
C++ 解法
複雜度分析
時間複雜度:O(n) — 迭代 n-1 次,每次做常數次運算。
空間複雜度:O(1) — 只使用五個變數。
虛擬碼
1. Initialize a = e = i = o = u = 1 (base case: strings of length 1) 2. For step from 1 to n-1: a. new_a = (e + i + u) % MOD b. new_e = (a + i) % MOD c. new_i = (e + o) % MOD d. new_o = i % MOD e. new_u = (i + o) % MOD f. Update a, e, i, o, u with new values 3. Return (a + e + i + o + u) % MOD
其他解法
矩陣快速冪 O(log n):將轉移規則表示為 5x5 矩陣,使用矩陣快速冪在 O(5^3 log n) = O(log n) 時間內求解。適合 n 極大的情況,但實作較複雜。
記憶化遞迴 O(5n):dp(pos, lastChar) 表示從位置 pos 開始、上一個字元為 lastChar 的方案數。時間空間皆 O(5n) = O(n),直覺但遞迴開銷稍大。
延伸思考
- 若規則改變(例如新增限制或移除某些限制),如何快速調整轉移方程?
- 當 n 極大(例如 10^18)時,如何利用矩陣快速冪加速?
- 若不只有五個母音,而是任意字母集合與任意轉移規則,如何泛化此解法?