DP 의 두가지 종류

DP 의 두가지 경우에 대해서 다시 한번 정리하고자 한다. 

우선 가장 쉬운 아래 문제에 대해서 DP 로 접근 해보자.

아래 처럼 사다리 처럼 삼각형으로 내려가면서 아래 혹은 오른쪽 아래로만 이동할경우 가장 큰 합은?

↓ 

↓ →

6
1	2
3	7	4
9	4	1	7
2	7	5	9	4

Top Down 반식 

위에서 아래로 내려오면서 값을 더하는 경우 

재귀로 풀어 보면 처음 부터 하나씩 증가 하면서 부분 증가 수열의 최대값을 구해 나가는 함수 

 

int DP(int idx) { int max_len = -1; if (arr[idx] != -1) return arr[idx]; for (int i = idx + 1; i <= N; i++) { if (in[idx] < in[i]) arr[idx] = max_len = MAX(max_len, DP(i)); } if (arr[idx] == -1){ return arr[idx] = 1; } else{ return  arr[idx] = max_len + 1; } }

Bottom up 방식 

아래에서 위로 올라오면서 값을 구하는경우 

for (i = N-1; i >= 0; i--) { for (int j = i + 1 ; j < N; j++) { if (v[j]  > v[i])  arr[i] = MAX(arr[i], arr[j] + 1); }                max = MAX(arr[i], max); }