Author: Adabelle Xie
Print out the nth number of the Fibonacci sequence (using the version of the sequence beginning with 1, not 0).
implement the bottom up or top down DP versions of finding the Fibonacci sequence. Link
This solution is fairly straightforward. Create a long array of length n. Each long in the array represents a number in the Fibonacci sequence. Make the first two elements 1 and 1, respectively, representing the first two numbers in the sequence. Run a for loop, with counter i starting at 2 and going until n. Each subsequent number in the sequence is equal to the sum of the previous two, the element at i-1 plus the element at i-2 and should be stored at index i in the array. After the loop is finished, return the last element in the array.
You can also solve this problem with a recursive method. The parameters are a long n and a long array memo. Your base cases will be n=0 and n=1, in which case return 1. Otherwise, if memo[n] is 0, meaning fib(n) has not been calculated yet, return fib(n-1) + fib(n-2). If memo[n] is not 0, that means it has already been calculated, in which case we can just return memo[n].
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.