dynamic progoramming 알고리즘

-memoization

 컴퓨터 프로그래밍을 실행할때 이전에 계산한 값을 메모리에 저장해서 매번 다시 계산하지 않도록 함

 

-동적계획 알고리즘

작은부분에서 큰부분의 해들을 모두 구하여 최종적으로 원래 주어진 문제를 해결하는 과정

여러개의 최적해중 임의의 최적해를 구하는것=>  optimal

 

-  문제를 더 작은 부분문제로 나눔

-함수의 호출을 줄이기 위함임!!

메모이제이션 예제

중복을 없애기 위해 저장된 결과를 배열에 저장해 다음에 사용할때는 저장된 값만 불러오는 방식으로 하는것

 

1.구하고자하는 문제를 여러  subproblem 으로 만든다

2.가장 작은 부분 문제(보통 0이나 1등의 종료조건)부터 푼 뒤 값을 저장한다. => 메모이제이션

3.메모이제이션된 부분 문제들의 해를 이용하여 차례로 더 큰 상위 문제의 답을 구한다.

4. (3)과정을 가장 큰 문제(구하고자 하는 큰 문제)에 도달할때까지 반복한다.

이건 그냥 예제 해보는게 답일듯

https://coding-all.tistory.com/28

[백준 문제 풀이] 2579 계단 오르기

어렵다 어려워..

 =>점화식 세우는게 제일 중요한듯

 

기본 동적계획법에 대한 강의만 들었음

문제 풀면서 이해하는게 더 좋을듯