DHPC1703 - Editorial

PROBLEM LINK:

Contest

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.

//