Giả sử chúng ta có một số n. Chúng ta phải tìm tổng của n số hạng Fibonacci đầu tiên (hệ số Fibonaccise lên đến n số hạng). Nếu câu trả lời quá lớn thì trả về kết quả modulo 10 ^ 8 + 7.
Vì vậy, nếu đầu vào là n =8, thì đầu ra sẽ là 33 vì một số số hạng Fibonacci đầu tiên là 0 + 1 + 1 +2 + 3 + 5 + 8 + 13 =33
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- m:=10 ^ 8 + 7
- memo:=một bản đồ mới
- Xác định một hàm giải quyết (). Điều này sẽ mất n, m
- nếu n có trong bản ghi nhớ, thì
- trả lại thư báo [n]
- memo [n]:=n khi n <2, ngược lại (giải (n-1, m) + giải (n-2, m)) mod m
- trả lại thư báo [n]
- Từ phương thức chính, lấy danh sách các giá trị ghi nhớ và lấy tổng của chúng.
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơ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])) Đầu vào
8
Đầu ra
33