สมมติว่าเรามีตัวเลข n เราต้องการหาผลรวมของพจน์แรก n ตัวของอนุกรมฟีโบนัชชี (ลำดับฟีโบนัชชียาว n พจน์) หากคำตอบมีขนาดใหญ่เกินไป ให้คืนค่าผลลัพธ์แบบ modulo 10^8 + 7
ตัวอย่างเช่น หาก n = 8 ผลลัพธ์จะเป็น 33 เนื่องจากพจน์แรกๆ ของฟีโบนัชชีคือ 0 + 1 + 1 + 2 + 3 + 5 + 8 + 13 = 33
ขั้นตอนการแก้ปัญหา
- กำหนด m := 10^8 + 7
- สร้าง memo เป็น dictionary ใหม่สำหรับเก็บค่าที่คำนวณแล้ว (Memoization)
- กำหนดฟังก์ชัน solve(n, m):
- ถ้า n อยู่ใน memo แล้ว ให้คืนค่า memo[n]
- memo[n] := n หาก n < 2 มิฉะนั้น (solve(n-1, m) + solve(n-2, m)) mod m
- คืนค่า memo[n]
- จากฟังก์ชันหลัก ให้ดึงค่าทั้งหมดใน memo มารวมกันแล้วหาผลรวม
ตัวอย่างโค้ด
m = 10**8 + 7
memo = {}
def solve(n, m):
if n in memo:
return memo[n]
memo[n] = n if n < 2 else (solve(n-1, m) + solve(n-2, m)) % m
return memo[n]
n = 8
solve(n, m)
print(sum(list(memo.values())[:n]))
อินพุต
8
เอาต์พุต
33
