[TIL] DP

주어진 문제가 최적화의 원칙을 만족해야만 동적 계획법을 적용할 수 있다.

(최적화의 원칙 : 어떤 문제에 대한 해가 최적일 때 그 해를 구성하는 작은 문제들의 해 역시 최적임)

DP는 문제의 순환적 성질 떄문에 이전에 계산되었던 작은 문제의 해가 어딘가에서 필요하게 되는데

이를 위해 DP에서는 이미 해결된 작은 문제들의 해를 어떤 공간(동적 Table)에 적용해야 한다.

 

DP에는 부분 문제들 사이에 의존적 관계가 존재하고 이 관계를 찾는게 DP문제 해결의 핵심이라고 볼 수 있다.

 

 

DP의 핵심은 메모이제이션!

상향(bottom-up)식방법은 통상 반복문으로 해결하고 하향식(top-down) 방법은 재귀로 해결한다.

 

---

 

Arrays.binarySearch( array , value ) 에서 value 가 array에 있다면 인덱스를 리턴

                                                     value가 array에 없으면 들어가야할 -(알맞은 삽입인덱스)-1 를 리턴한다. (0떄문에 -1를 뺴는 작업을 내부적으로 하는 듯)