종만북 dp 개론 미완

<dp란>

 

문제를 쪼개어 부분 문제로 나누고, 이 답들로부터 원래 문제에 대한 답을 계산하는 알고리즘

이 때, 중복된 부분 문제에 대해서는 메모이제이션을 해서 계산 시간을 줄인다.

 

<분할 정복과 비슷해 보이는데?>

 

두 개의 차이점 : 문제를 나누는 방식

 

p208 그림8.1

 

 

<시간 복잡도>

 

(존재하는 부분 문제의 수) * (한 부분 문제를 풀 때 필요한 반복문의 수행 횟수)

 

 

 

<코드>

 

dp문제를 푸는 첫 단계는 해당 문제를 재귀적으로 해결하는 완전 탐색 알고리즘을 만드는 것이다.

 

int cache[50][50];
int dp(int a, int b){
	//기저사례
	if(...) return ...;
    
    //중복방문
    int &res = cache[a][b];
    if(res != -1) return res;
    
    //답 계산
    ...
    return res;
}

int main(){
	memset(cache, -1, sizeof(cache));
}