โปรแกรมนับสตริงสระที่เรียงลำดับแล้วใน Python

ปัญหา

ให้ n หาจำนวนสตริงความยาว n ที่ประกอบด้วยสระ a,e,i,o,u และเรียงตามลำดับตัวอักษร (non-decreasing)

ตัวอย่าง

n=2 → 15 (aa, ae, ai, ao, au, ee, ei, eo, eu, ii, io, iu, oo, ou, uu)

ขั้นตอนการแก้ปัญหา

1. ถ้า n == 1: คืน 5
2. count := [1]*6 (index 1..5 แทน a..u)
3. วน i 3 ถึง n:
   • count[1] += count[2]+count[3]+count[4]+count[5]
   • count[2] += count[3]+count[4]+count[5]
   • count[3] += count[4]+count[5]
   • count[4] += count[5]
4. total := sum(i * count[i] for i in 1..5)
5. คืน total

การนำไปใช้งาน (Python)

def solve(n):
    if n == 1:
        return 5
    count = [1 for i in range(6)]
    for i in range(3, n + 1):
        count[1] = count[1] + count[2] + count[3] + count[4] + count[5]
        count[2] = count[2] + count[3] + count[4] + count[5]
        count[3] = count[3] + count[4] + count[5]
        count[4] = count[4] + count[5]
    total = 0
    for i in range(1, 6):
        total += i * count[i]
    return total

n = 2
print(solve(n))

อินพุต

2

เอาต์พุต

15