สมมติว่าเรามีตัวเลข n เราต้องหาผลรวมของ n เทอมฟีโบนักชี (Fibonaccisequence ถึง n เทอม) หากคำตอบมีขนาดใหญ่เกินไป ให้ส่งคืนผลลัพธ์ modulo 10^8 + 7
ดังนั้น หากอินพุตมีค่าเท่ากับ n =8 ผลลัพธ์จะเป็น 33 เนื่องจากเงื่อนไขฟีโบนักชีสองสามตัวแรกคือ 0 + 1 + 1 +2 + 3 + 5 + 8 + 13 =33
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- ม :=10^8+7
- บันทึก :=แผนที่ใหม่
- กำหนดฟังก์ชัน Solve() นี่จะใช้เวลา n, m
- ถ้า n อยู่ในบันทึกช่วยจำ
- บันทึกการส่งคืน[n]
- ข้อควรจำ[n] :=n เมื่อ n <2 มิฉะนั้น (แก้(n-1, m) +solve(n-2, m)) mod m
- บันทึกการส่งคืน[n]
- จากวิธีหลัก รับรายการค่าบันทึกและนำผลรวม
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
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
