(C++) - LeetCode (easy) 509. Fibonacci Number

https://leetcode.com/problems/fibonacci-number/description/

Fibonacci Number - LeetCode

top down dp로 해결한 문제였습니다.

📕 풀이방법

📔 입력 및 초기화

fibonacci 숫자를 저장할 배열 fibNum을 선언 후 생성자에서 모든 방의 원소를 -1로 초기화해줍니다.

📔 풀이과정

1. 기저 case에서 n이 0이면 0을, n이 1이면 1을 반환합니다.

2. memoization을 사용해 -1이 아닌 원소는 함수를 재귀적으로 호출하지 않고 바로 값을 반환하는 방식으로 시간 복잡도를 줄일 수 있습니다.

3. 이 외의 경우에는 fib(n-1) + fib(n-2) 값을 반환해줍니다.

📔 정답 출력 | 반환

fib함수의 결과를 반환합니다.

---

📕 Code

📔 C++

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

---

*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.