참고 : 백준 - 다이나믹 프로그래밍 시작하기

Dynamic Programming

• 큰 문제를 작은 문제로 나눠서 푸는 알고리즘
• Overlapping Subproblem
• Optimal Substructure

Overlapping Subproblem

• 큰 문제와 작은 문제를 같은 방법으로 풀 수 있다.
• 문제를 작은 문제로 쪼갤 수 있다.

문제의 정답을 작은 문제의 정답에서 구할 수 있다.

예시

서울에서 부산을 가는 가장 빠른 길이 대전과 대구를 순서대로 거쳐야 한다면 대전에서 부산을 가는 가장빠른 길은 대구를 거쳐야 한다.

Optimal Substructure

• 큰 문제와 작은 문제를 같은 방법으로 풀 수 있다.
• 문제를 작은 문제로 쪼갤 수 있다.

작성중