[Algorithm] 동적 계획법(Dynamic Programming)

동적 계획법(Dynamic Programming)

• 복잡한 문제를 여러 개의 간단한 문제로 분리하여 부분의 문제들을 해결함으로써 최종적으로 복잡한 문제의 답을 구하는 방법

원리와 구현 방식

1. 큰 문제를 작은 문제로 나눌 수 있어야 한다
2. 작은 문제들이 반복되어 나타나고 사용되며 이 작은 문제들의 결괏값은 항상 같아야 한다
3. 모든 작은 문제들은 한 번만 계산해 DP 테이블에 저장하며 추후 재사용할 때는 DP 테이블을 이용한다
   • 이를 메모이제이션(Memoization) 기법이라고 한다
4. 동적 계획법은 top-down 방식과 bottom-up 방식으로 구현할 수 있다
   • top-down은 주로 재귀 함수, bottom-up은 반복문으로 구현한다

피보나치 수열의 점화식

$DP[i] = DP[i-1] + DP[i-2]$

조합 점화식

$DP[i][j] = DP[i-1][j] + DP[i-1][j-1]$

완전순열 점화식

$DP[i] = (N-1)*(DP[N-1] + DP[N-2])$