[DP - 1D, Easy] N-th Tribonacci Number

https://leetcode.com/problems/n-th-tribonacci-number/description/?envType=study-plan-v2&envId=leetcode-75

흔히 보는 피보나치 수열 문제하고 동일한 논리다. 하나 늘었다고 해서 다를 건 없다.

bottom-up 또는 top-down DP로 풀 수 있겠다.

• bottom-up: 3가지 변수를 매 순회마다 갱신, 최종적으로 갱신된 값 리턴
• top-down: 메모이제이션 배열 n-3 n-2 n-1 사용

탑다운 방식

class Solution {
    public int tribonacci(int n) {
        if (n == 0) {
            return 0;
        }
        if (n <= 2) {
            return 1;
        }
        
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 1;

        for (int i=3; i<=n; i++) {
            dp[i] = dp[i - 3] + dp[i - 2] + dp[i - 1];
        }

        return dp[n];
    }
}

바텀업 방식

class Solution {
    public int tribonacci(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1 || n == 2) {
            return 1;
        }

        int a = 0, b = 1, c = 1;
        for (int i = 3; i <= n; i++) {
            int next = a + b + c;
            a = b;
            b = c;
            c = next;
        }

        return c;
    }
}