숫자 n이 있다고 가정합니다. 우리는 처음 n개의 피보나치 항(최대 n항까지의 피보나치 수열)의 합을 찾아야 합니다. 답이 너무 크면 결과 모듈로 10^8 + 7을 반환합니다.
따라서 입력이 n =8과 같으면 처음 몇 개의 피보나치 항이 0 + 1 + 1 +2 + 3 + 5 + 8 + 13 =33이므로 출력은 33이 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- m :=10^8+7
- 메모:=새 지도
- solve() 함수를 정의합니다. n, m 소요됩니다.
- n이 메모에 있으면
- 반품 메모[n]
- memo[n] :=n 일 때 n <2 그렇지 않으면 (solve(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