Chương trình đếm số chuỗi độ dài n thỏa mãn quy tắc ngữ pháp trong Python

Cho số , đếm số chuỗi độ dài chỉ chứa nguyên âm [a, e, i, o, u] tuân theo quy tắc chuyển tiếp:

• a → chỉ e
• e → a hoặc i
• i → không phải i
• o → i hoặc u
• u → chỉ a

Kết quả modulo 10⁹+7.

Ví dụ: → 10 chuỗi: ["ae", "ea", "ei", "ia", "ie", "io", "iu", "oi", "ou", "ua"].

Giải thuật (Dynamic Programming O(n))

1. Khởi tạo (độ dài 1).
2. Lặp lần:
   • (theo quy tắc chuyển tiếp ngược).
3. Trả về .

Ví dụ minh họa

class Solution:
    def solve(self, n):
        m = 10**9 + 7
        if n == 0:
            return 0
        a = e = i = o = u = 1
        for _ in range(n-1):
            a, e, i, o, u = e+i+u, a+i, e+o, i, i+o
        return (a + e + i + o + u) % m

ob = Solution()
print(ob.solve(3))  # Output: 19

Đầu vào

3

Đầu ra

19