동적 계획법

상향식 접근법으로, 가장 최하위 해답을 구한 후, 이를 저장하고, 해당 결과값을 이용해서 상위 문제를 풀어가는 방식Memoization 기법을 사용함

모든 경우의 수를 완전 탐색할 때 사용

하위의 문제들이 중복되어 재활용되는 특징이 있음

 

대표 예시 - 피보나치 수열

def fibo_dp(num):
    cache = [ 0 for index in range(num + 1)]
    cache[0] = 0
    cache[1] = 1
    
    for index in range(2, num + 1):
        cache[index] = cache[index - 1] + cache[index - 2]
    return cache[num]

 

문제

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

(1 ≤ n ≤ 1,000)

 

정리

1. 입력값만큼 빈리스트 만들기

2. 초깃값 만들기 (할당한 값을 재사용하는 동적 계획법의 특징)

3. 반복문으로 계산되는 로직 만들기

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

for index in range(3, 1001):
    dp[index] = dp[index - 1] + dp[index - 2]
    
print (dp[n] % 10007)