1. 동적 프로그래밍 방법의 원리

문제의 크기가 작은 소문제에 대한 를 저장해 놓고, 이를 이용하여 크기가 보다 큰 문제의 해를 점진적으로 만들어가는 상향식 접근 방법

  • 각 작은 문제는 원래의 문제와 동일한 문제이지만 입력의 크기만 작음
  • 입력의 크기가 아주 작은 단순한 문제가 되면 쉽게 해를 구할 수 있고, 이를 테이블에 저장
  • 이후 해당 소문제의 해가 필요할 때마다 테이블에 저장된 결과를 바로 이용

동적 프로그래밍 dynamic programming => 동적 계획법 (타 서적, 교육에서는 동적 계획법이라 많이 부른다.)

  • 컴퓨터에서의 프로그램과는 무관, 해를 구축하는 테이블을 이용한다는 의미

최솟값/최댓값을 구하는 최적화 문제에 적용

2. 피보나치 수열 문제

 

3. 연쇄 행렬 곱셈 문제