[백준][동적계획법1]

피보나치 수2

def fibonacci(n):
    dp = [0,1]
    for i in range(2,n+1):
        temp=dp[i-1]+dp[i-2]
        dp.append(temp)
    return dp[n]

n = int(input())
print(fibonacci(n))

피보나치 함수

def fibonacci(n):
    dp = [[1,0],[0,1],[1,1]]
    if n==0:
        return dp[0]
    elif n==1:
        return dp[1]
    elif n==2:
        return dp[2]
    for i in range(3,n+1):
        temp0=dp[i-1][0]+dp[i-2][0]
        temp1=dp[i-1][1]+dp[i-2][1]
        dp.append([temp0,temp1])
    return dp[n]

N = int(input())
for _ in range(N):
    n = int(input())
    result = fibonacci(n)
    print(result[0],result[1],sep=' ')

01타일

def function(n):
    dp = [None,1,2]
    if n==1:
        return 1
    elif n==2:
        return 2
    for i in range(3,n+1):
        temp=(dp[i-1]+dp[i-2])%15746
        dp.append(temp)
    return dp[n]

N = int(input())
print(function(N))

파도반 수열

def function(n):
    dp = [None,1,1,1,2,2,3]
    if n in [1,2,3,4,5,6]:
        return dp[n]
    for i in range(7,n+1):
        temp = dp[i-1]+dp[i-5]
        dp.append(temp)
    return dp[n]

N = int(input())
for _ in range(N):
    n = int(input())
    print(function(n))