크기가 작은 부분 문제를 해결 한 후, 점점 크기를 증가시켜서 부분적으로 문제 해결을 함으로써 최종 무제를 해결하는 알고리즘 입니다.
상향식 접근법으로, 가장 작은 크기의 해답을 구하는 것으로 시작으로, 조금씩 더 큰 문제의 해답을 구하고, 해당 결과값들로 상위 문제들을 푸는 방식입니다.
이때, memoization 기법을 사용합니다.
Memization 기법이란, 이전에 문제의 값을 저장함으로써, 다음에 이전에 계산한 값을 필요로 할때 다시 계산하지 않고 저장한 값을 사용하도록해서 실행 속도를 빠르게 해주는 기법입니다.
동적 계획법(Dynamic Programming/DP)를 이용해서 푸는 가장 대표적인 문제는 피보나치 수열입니다.

0. 피보나치 수열

(https://www.fun-coding.org/00_Images/Fibonacci.png)

def myFibo_dp(num):
    cache = [i for i in range(num+1)]
    
    for i in range(2, num+1):
        cache[i] = cache[i-1] + cache[i-2]
    
    return cache[num]   

1. 백준 11726: 2×n 타일링

https://www.acmicpc.net/problem/11726
해당 문제는 단순한 문제로써, n의 값이 1부터 5일때까지만 계산해 보아도, 패턴을 찾고 점화식을 구할수 있습니다. 점화식은 n >=3 일때, F(n) = F(n-1) + F(n-2) 입니다.

def cal_comb(n):
    if n <= 2:
        return n
    cache = [0 for i in range(n+1)]
    cache[1] = 1
    cache[2] = 2
    
    for i in range(3, n+1):
        cache[i] = cache[i - 1] + cache[i - 2]
    
    return cache[n]%10007

n = int(input())
print(cal_comb(n))

2. 백준 9461: 파도반 수열(Padovan Sequence)

https://www.acmicpc.net/problem/9461
판도반 수열 또한 n의 값을 1부터 시작해서 n의 값을 1씩 늘려가면서 값들을 확인해보면 점화식을 찾을 수 있습니다.
1 <= n <= 3 일때, F(n) = 1.
3 < n <= 5 일때, F(n) = 2.
5 < n 일때, F(n) = F(n-1) + F(n-5).

def padovan_sequence(n):
    if n <= 3:
        return 1
    elif n <= 5:
        return 2
    cache = [0 for i in range(n+1)]
    cache[1] = 1
    cache[2] = 1
    cache[3] = 1
    cache[4] = 2
    cache[5] = 2
    
    for i in range(6, n+1):
        cache[i] = cache[i-1] + cache[i-5]
        
    return cache[n]
    
t = int(input())
for i in range(t):
    n = int(input())
    print(padovan_sequence(n))

3. 백준 1904: 01타일

https://www.acmicpc.net/problem/1904
해당 문제의 점화식은,
1 <= n <= 2 일때, F(n) = n.
2 < n 일떄, F(n) = F(n-1) + F(n-2) 입니다.

def tiles(n):
    if n <= 2:
        return n
    
    cache = [0 for i in range(n+1)]
    cache[1] = 1
    cache[2] = 2

    for i in range(3, n+1):
        cache[i] = (cache[i-1]+ cache[i-2])%15746
        
    return cache[n]

n = int(input())
print(tiles(n))```