동적 계획법

다이나믹 프로그래밍은 메모리 공간을 약간 더 사용해서 연산 속도를 비약적으로 증가시키는 방법이다. 우선 다음과 같은 2가지 조건을 만족할 때 다이나믹 프로그래밍을 사용할 수 있다.

 

1. 큰 문제를 작은 문제로 나눌 수 있다.
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

단순 반복문을 활용하는 Bottom-Up 방식으로 다이나믹 프로그래밍 방법을 해결

 

 

여기서 부분 문제 반복과 최적 부분 구조를 가지고 있다에서
부분 문제의 해는 전체 문제의 해를 구할 때 필요해야한다.

하향식 Bottom-Up 방식이라고도 한다.
최초 값부터 차례대로 계산해 나가는 방식이다.

 

 

복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법