(C++) - LeetCode (easy) 1137. N-th Tribonacci Number

https://leetcode.com/problems/n-th-tribonacci-number/description/

N-th Tribonacci Number - LeetCode

dp 문제였습니다.

📕 풀이방법

📔 입력 및 초기화

생성자에 class instance화시 값을 저장할 vector 변수를 선언해줍니다.* 값이 int 범위(약 21억)을 초과하지 않기 때문에 int로 선언해줍니다.

📔 풀이과정

top down dp로 구현해줍니다. 중복 함수 호출이 발생해 시간복잡도가 O(n^3)이 되는 것을 한번만 계산하면 되도록 구현합니다. 이는 memoization으로 가능합니다.

📔 정답출력

계산 결과를 반환합니다.

---

📕 Code

📔 C++

class Solution {
public:
    vector <int> d;
    Solution(){
        d = vector <int>(40,0);
    }    
    int tribonacci(int n) {
        if(!n) return 0;
        if(n == 1 || n == 2) return 1;
        int &ret = d[n];
        if(ret != 0) return ret;
        return ret = tribonacci(n - 1) + tribonacci(n - 2) + tribonacci(n - 3);
    }
};

---

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