Chương trình đếm chuỗi nguyên âm đã sắp xếp trong Python

Cho n. Đếm số chuỗi độ dài n chỉ chứa nguyên âm (a,e,i,o,u) và sắp xếp theo thứ tự từ điển (không giảm).

Ví dụ: n=2 → 15: aa, ae, ai, ao, au, ee, ei, eo, eu, ii, io, iu, oo, ou, uu.

Giải thuật (Đếm tổ hợp / DP)

1. Nếu n==1: trả về 5.
2. Mảng count[1..5] = 1 (số chuỗi kết thúc bằng a/e/i/o/u).
3. Lặp i từ 3 đến n (điều chỉnh: thực tế lặp từ 2 đến n):
   • Cập nhật ngược: count[1] += count[2]+...+count[5], count[2] += count[3]+...+count[5], ...
4. Tổng = sum(i * count[i] for i in 1..5).

Lưu ý: code gốc có lỗi vòng lặp (bắt đầu từ 3), logic đúng là DP: dp[i][j] = số chuỗi độ dài i kết thúc bằng nguyên âm thứ j.

Ví dụ minh họa

def solve(n):
    if n == 1:
        return 5
    count = [1] * 6  # index 1..5
    for _ in range(2, n + 1):
        for i in range(1, 5):
            count[i] = sum(count[i:6])
    total = sum(i * count[i] for i in range(1, 6))
    return total

n = 2
print(solve(n))

Đầu vào

2

Đầu ra

15