[알고리즘] 동적계획법

# 동적계획법

 동적계획법은 분할정복법과는 정반대의 방식을 이용하여 문제를 해결한다. 동적계획법은 문제를 더 작은 문제로 분할한다는 점에서는 분할정복법과 비슷하지만 여기서는 작은 문제를 먼저 해결하고 저장하고 다른 계산에 그 저장된 결과를 이용한다.

 동적계획법은 상향식 접근 방법(bottom-up)이다. 계획이란 해답을 구축하는데 배열을 사용함을 의미한다.

# 예시

 파스칼의 삼각형이 비슷한 예시가 되겠다.

 원하는 결과를 얻기까지 결과값들을 배열에 저장하여 그 값을 다음 계산에 이용한다.

int bin(int n, int k){

index i, j;

int B[0..n][0,,k];

for( i = 0 ; i <= n ; i++ ){

for( j = 0 ; j <= min( i , k ) ; j++ ){

if( j == 0 || j == i )

B[i][j] = 1;

else

B[i][j] = B[i-1][j-1] + B[i-1][j];

}

}

return B[n][k];

}