다이나믹 프로그래밍을 사용하는 경우
1. 큰 문제를 작은 문제로 나눌 수 있을 때
2. 작은 문제에서 구한 정답이 큰 문제에서도 같을 때

부분문제들의 중복여부를 확인해서 자잘한것이 중복이 많이되면 탐색이 아니라 다이나믹 알고리즘 이라는 것을 알아차려야 함!

다이나믹 프로그래밍

큰 문제를 작게 나누고 , 같은 문제는 한번씩만 풀어서 해결하기

재귀와 반복문을 이용할 수 있는데 반복문을 이용하는 것이 성능에 더 좋다

Top-Down (탑다운 방식)

재귀
한번 구한 결과를 계속해서 다시 사용하는 방법

메모이제이션 (=캐싱 Caching)

한번 구한 결과를 메모해두고 같은 식을 다시 호출하면 그대로 가져오는 기법

Bottom-Up (보텀업 방식)

반복문
결과 저장용으로 d[] 배열을 만들고 그 값들을 차곡차곡 비교해 (max , min) 결과 값을 구하는 법

DP 테이블

결과 저장용 리스트

문제 접근 방법

일단은 반복문을 사용하는 것이 성능상 좋다.
1. 전체를 부분으로 나누자
2. 부분 값을 구할 수 있는 점화식을 세우자
예시)

a[i] = min(a[i-1], a[i//2])

🪄 나만의 풀이 루틴

1. 찾고자 하는 값 or 계산된 결과를 저장할 DP 테이블 생성
m+1 등을 하는 이유는 배열이 0부터 시작하는데 각 index와 계산할 값을 맞추기 위해서이다.

d = [0]*10001
d = [10001] * (m+1)

2. d의 초기 값 지정 (d[1] , d[2])

d[1] = 1
d[2] = 3

3. d의 범위 or 입력받은 범위만큼 반복문

for i in range(2,n):
	d[i] = min(d[i-1], d[i-2]+1 )

이런 방식으로 다이나믹 프로그래밍을 접근하고 있다.!