백준 알고리즘 9507번 Generations of Tribbles(python)

기본적인 다이나믹 프로그래밍 문제이다.

def koong(n):
    if n < 2:
        return 1
    if n == 2:
        return 2
    if n == 3:
        return 4
    if dp[n]:
        return dp[n]
    dp[n] = koong(n-1) + koong(n-2) + koong(n-3) + koong(n-4)
    return dp[n]
    
dp = [0]*68
for _ in range(int(input())):
    n = int(input())
    print(koong(n))