(작성중)Dynamic Programming
동적 프로그래밍(X) 동적 계획법(O)동적 계획법과 분할 정복의 차이가 발생하는 부분은 문제를 나누는 방식. 동적 계획법에서 어떤 부분 문제는 두 개 이상의 문제를 푸는데 사용될 수 있다. 이렇게 두 번 이상 계산되는 부분 문제를 중복되는 부분 문제(overlapping subproblems)라고 한다.동적 계획법 알고리즘의 가장 유명한 예 중 하나는 이항 계수(binomial co-efficient)의 계산이다. 이항계수는 n개의 서로 다른 원 소 중에서 r개의 원소를 순서없이 골라내는 방법의 수를 나타내는 것으로, 이항 계수에는 다음과 같은 점화식이 성립한다.nCr = n-1Cr-1 + n-1Cr public int bino(int n, int r){ // 기저 사례: n=r(모든 원소를 다 고르는 ..
2017. 6. 26. 23:34