[Java/Python] leetcode 1137. N-th Tribonacci Number

문제

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

N-th Tribonacci Number - LeetCode

트라이보나치 수열 값을 구해서 리턴할 것.

알아야 할 개념

• 메모이제이션

풀이

풀이는 다음과 같다. 

• 현재 값 n 일때 트라이보나치 값을 메모할 배열을 만들고 초기화를 한다. 
• 현재 값이 메모돼있으면, 그 값을 리턴
• 재귀로 n-1, n-2 , n-3 값을 확인하여 현재 값에다 저장하고 리턴한다. 

 

코드

자바

class Solution {
    int memo[];
    public int tribonacci(int n) {
        memo = new int[38];
        Arrays.fill(memo, -1);
        memo[0] = 0;
        memo[1] = 1;
        memo[2] = 1;
        return helper(n);
    }
    public int helper(int n){
        if(memo[n] > -1)return memo[n];
        for(int i = 1 ;i < 4 ;i++)
            memo[n-i] = helper(n-i);
        return memo[n] = memo[n-1] + memo[n-2] + memo[n-3];
    }
}

파이썬

 

class Solution:
    def tribonacci(self, n: int) -> int:
        memo = [0]*3
        memo[0] = 0
        memo[1] = 1 
        memo[2] = 1
        for i in range(3,n+1):
            memo.append(memo[i-1]+memo[i-2]+memo[i-3])
        return memo[n]