내일은 알고리즘

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

피보나치 문제와 99.9% 똑같지만 점화식이 이전의 세 수를 더한다는 차이점이 있습니다.

그러니 이름이 트리보나치겠죠? 간단하게 풀이했습니다.

class Solution:
    def tribonacci(self, n: int) -> int:
        dp = [0] * (38)
        dp[0] = 0
        dp[1] = 1
        dp[2] = 1

        for i in range(3,n+1):
            dp[i] = dp[i-1] + dp[i-2] + dp[i-3]

        return dp[n]

for i in range(0,26):
    print(Solution().tribonacci(i))

https://leetcode.com/problems/fibonacci-number/

정말 유명한 피보나치 DP문제입니다.

매번 피보나치 수를 새로 계산하지 않고 이전의 결과값을 사용해 계산하면 됩니다.

Memoization의 개념과 필요성을 한방에 이해시키는 좋은 문제라고 생각합니다.

class Solution:
    def fib(self, n: int) -> int:
        dp = [0] * (31)
        dp[0] = 0
        dp[1] = 1

        for i in range(2,n+1):
            dp[i] = dp[i-1] + dp[i-2]

        return dp[n]

for i in range(0,31):
    print(Solution().fib(i))