PROBLEM LINK:
Author: Adabelle Xie
DIFFICULTY:
Easy-Medium
PREREQUISITES:
DP, knowledge of the Fibonacci sequence is helpful but not necessary
PROBLEM:
Print out the nth number of the Fibonacci sequence (using the version of the sequence beginning with 1, not 0).
QUICK EXPLANATION:
implement the bottom up or top down DP versions of finding the Fibonacci sequence. Link
EXPLANATION:
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.
ALTERNATIVE SOLUTION:
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.