Leetcode - 1137. N-th Tribonacci Number

문제

다음을 만족하는 Tribonacci 수열이 존재할때 값을 계산하기.

T0 = 0, T1 = 1, T2 = 1, and Tn+3 = Tn + Tn+1 + Tn+2 for n >= 0.

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

해결 O(N)

재귀를 배울때 항상나오는 피보나치 + DP 문제와 동일. dp[] 배열에 결과를 저장하면 함수콜을 할 필요없이 이미 한번 계산했던것은 배열값을 쓰면 됨. 시간복잡도는 O(N).
추가로, 모든 테스트케이스에서 모든 입력값들의 dp[i]는 동일하기 때문에, 전역변수로 써도됨.(오히려 테스트케이스가 누적될수록 겁나 빠른 결과가 나온다. 개이득인 부분) 그래서 결과도 겁나 빠르게 나옴 100%.

Runtime: 0 ms, faster than 100.00% of C online submissions for N-th Tribonacci Number.
Memory Usage: 5.4 MB, less than 97.69% of C online submissions for N-th Tribonacci Number.

1. Constraints.
 - input size:  0 <= n <= 37
 - return type: int
 - 
2. Ideas
 - DP + memoization -> O(N) / O(N)
   - dp[n] is same on the every test case input n 
3. Test Cases
 - assert(tribonacci(0) == 0)
 - assert(tribonacci(1) == 1)
 - assert(tribonacci(2) == 1)
 - assert(tribonacci(3) == 2)
 - assert(tribonacci(25) == 1389537)
 
4. Coding

그리고 dp[n] 값 리턴하는 라인을 가장 먼저하는게 더 빠르다.

int dp[38] = {0};
int tribonacci(int n){
    if (dp[n])
        return dp[n];
    if (n == 0)
        return 0;
    if (n == 1 || n == 2)
        return 1;
    dp[n] = tribonacci(n-1) + tribonacci(n-2) + tribonacci(n-3);
    return dp[n];
}