287. Memo Fibonacci
A gardener grows a strange vine. In week 0 it carries 0 leaves and in week 1 it carries 1 leaf. From week 2 onward the vine carries exactly as many leaves as it carried in the previous week plus the week before that.
Given the week number n, return how many leaves the vine carries that week. A direct recursive call recomputes the same weeks again and again and needs exponential time, so store the answer for every week the first time you compute it and reuse it afterwards.
Example 1
- Input:
- n = 19
- Output:
- 4181
- Explanation:
The leaf counts run 0, 1, 1, 2, 3, 5, 8, ... and week 19 carries 4181 leaves.
Example 2
- Input:
- n = 33
- Output:
- 3524578
- Explanation:
Week 33 carries 3524578 leaves.
Constraints
0 ≤ n ≤ 46
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(n)
- Space
- O(n)