[알고리즘] 다이나믹 프로그래밍

목적: 경우의 수가 너무 많아서 속도가 느려지는 문제를 개선하고자 수행시간을 단축하고자 만들어진 알고리즘

 

기억하기 알고리즘, 기억하며 풀기

 

1. DFS/BFS 로 풀 수는 있지는 경우의 수가 너무 많은 문제

2. 경우의 수들에 중복적인 연산이 많은 경우

 

#1463

n = int(input())
dp = [0]*(n+1)

for i in range(2,n+1):
    dp[i]=dp[i-1]+1
    if(i%2==0):
        dp[i]=min(dp[i],dp[i//2]+1)
    if(i%3==0):
        dp[i]=min(dp[i],dp[i//3]+1)

print(dp[n])

 

# 11726

import sys
n=int(sys.stdin.readline())
dp=[0]*1001
dp[1]=1
dp[2]=2
for i in range(3,n+1):
    dp[i]=(dp[i-1]+dp[i-2])%10007
print(dp[n])

 

#11727

n=int(input())
dp=[0]*(1001)
dp[1]=1
dp[2]=3
for i in range(3,n+1):
    dp[i]=(dp[i-2]*2+dp[i-1])%10007
print(dp[n])

 

#9095

T=int(input())
dp = [0]*12
dp[1]=1
dp[2]=2
dp[3]=4
for i in range(4,12):
    dp[i]=dp[i-3]+dp[i-2]+dp[i-1]

for tc in range(T):
    n = int(input())
    print(dp[n])

 

#11052

n = int(input())
cards = [0]+list(map(int,input().split()))
dp = [0 for _ in range(n+1)] 

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

print(dp[-1])

 

#16194

n = int(input())
cards = [0] + list(map(int,input().split()))
dp= cards
for i in range(1,n+1):
    for k in range(1,i+1):
        dp[i]=min(dp[i],cards[k]+dp[i-k])
    
print(dp[-1])

 

#11053

#11053
n = int(input())
nums = list(map(int,input().split()))
dp = [1]*n
for i in range(1,n):
    for j in range(i):
        if nums[i]>nums[j]:
            dp[i] = max(dp[i],dp[j]+1)
print(max(dp))

 

#14002

#14002
n = int(input())
nums = list(map(int,input().split()))
dp = [1]*n
for i in range(1,n):
    for j in range(i):
        if nums[i]>nums[j]:
            dp[i] = max(dp[i],dp[j]+1)

answer = []
x=max(dp)
print(x)
for i in range(n-1,-1,-1):
    if dp[i]==x:
        answer.append(nums[i])
        x-=1
answer.reverse()
print(' '.join(map(str,answer)))

 

#10844

n=int(input())
dp = [[0]*10 for _ in range(n+1)]
for i in range(1,10):
    dp[1][i]=1
for i in range(2,n+1):
    for j in range(10):
        if j==0:
            dp[i][j] = dp[i-1][1]
        elif j ==9:
            dp[i][j] = dp[i-1][8]
        else:
            dp[i][j] = dp[i-1][j-1]+dp[i-1][j+1]
print(sum(dp[n])%1000000000)