Dynamic Programming

Dynamic Programming 동적 프로그래밍이란 문제의 크기가 작은 소문제에 대한 해를 저장해 놓고, 이를 이용하여 크기가 보다 큰 문제의 해를 점진적으로 만들어가는 상향식 접근 방법이다. 각각의 소문제는 원래의 문제와 동일하지만 입력의 크기에 줄어듦 입력 크기가 아주 작은 단순한 문제가 되면 쉽게 해를 구할 수 있고, 이런 소문제의 해는 다시 사용될 수 있으므로 테이블에 저장 해당 소문제의 해가 필요할 때마다 테이블에서 결과를 바로 이용한다. 유형: