[LeetCode] 509. Fibonacci Number

 

https://leetcode.com/problems/fibonacci-number/description/?envType=study-plan-v2&id=dynamic-programming 

Fibonacci Number - LeetCode

문제 유형 : 다이나믹 프로그래밍

난이도 : Easy

 

문제

The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), for n > 1.

Given n, calculate F(n).

 

다이나믹 프로그래밍의 기본 피보나치 수열 문제이다.

 

입력

Fib(n)에 들어갈 n(0 <= n <= 30)이 주어진다.

 

출력

fib(n)의 값을 리턴한다.

 

아이디어

간단한 피보나치 수열이므로, 캐싱을 구현하여 풀어준면 된다.

class Solution {
    int cache[31];
public:
	Soultion(){
    memset(cache, -1, sizeof(cache);
    }
    int fib(int n) {
        if(n == 0){
            return 0;
        }
        if(n == 1){
            return 1;
        }
        if(cache[n] != -1){
            return cache[n];
        }
        cache[n] = fib(n-2) + fib(n-1);
        return cache[n];
    }
};