동적 프로그래밍

필요한 계산 값을 저장해뒀다가 재사용하는 알고리즘
즉, 반복적으로 계산되는 경우를 없애는 방법 !

예시문제
<백준 문제> 9095 - 1,2,3 더하기
1,2,3으로 만들 수 있는 경우의 수를 구하는 문제

T= int(input())
s=[1,2,4]+[0]*7

for i in range(3,10):
    s[i]=s[i-1]+s[i-2]+s[i-3]
for t in range(T):
    n=int(input())
    print(s[n-1])

4= 1+3 2+2 3+1이기에
1,2,3의 만드는 방법을 더해주면 된다.
또한, 예를 들어
7 = 1+6 = 2+5 = 3+4 라서
6을 만드는 수+5를 만드는 수+4를 만드는 수가 되는 것

그래서 계산되는 수를 저장해놓으면 된다 !