Dynamic Programmin

• 다이나믹 프로그래밍이란 ?

큰 문제를 작은 문제로 나누어 푸는 방법은 두가지 이다.

• 분할정복 : 중복이 허용되지 않는다.

• 다이나믹 프로그램 : 큰 문제가 작은 문제로 나누어 졌을 때 작은 문제들의 중복이 허용이 된다.

Dynamic Programming 로직

• 모든 작은 문제들은 한번만 풀어야 합니다.
  따라서 정답을 구한 작은 문제를 어딘가에 메모해 놓습니다.
  다시 그보다 큰 문제를 풀어나갈 때 똑같은 작은 문제가 나타나면 앞서 메모한 작은 문제의 결과값을 이용합니다.

그럼 언제 다이나믹 프로그래밍을 사용해야할까??

• 작은 문제가 반복이 일어나는 경우
• 같은 문제는 구할 때마다 정답이 같다.

참고자료 :
https://lee-seul.github.io/algorithm/2017/03/16/dynamic-programming.html