99클럽 코테 스터디 38일차 - DP

문제

N-th Tribonacci Number

풀이

• 피보나치인데 3개의 수에 대한 피보나치
• 재귀 과정에서 중복이 발생하므로 memo를 해줘야 한다

코드

class Solution {
    private int[] memo;
    
    public int tribonacci(int n) {
        memo = new int[n + 1];
        
        return recur(n);
    }
    
    public int recur(int n){
        if(n == 0) return 0;
        if(n == 1 || n == 2) return 1;
        
        if(memo[n] != 0) return memo[n];
        
        memo[n] = recur(n - 1) + recur(n - 2) + recur(n - 3);
        return memo[n];
    }
}

정리

• 피보나치는 괜춘괜춘