DP 정복 - 3.2 하향식 접근 방법과 상향식 접근 방법

이번 절은 지난 절과 거의 유사한 이야기를 좀 더 길게 해 놓은 거 같다.

하향식 접근법은 재귀 호출(메모이제이션 포함)

상향식 접근법은 다이나믹 프로그래밍.

 

하향식 접근의 가장 간단한 예제는 이진트리의 순회에 대한 내용을 설명한다.

 

상향식 다이내믹 프로그래밍이 좋지 않은 경우

- 때에 따라서는 하향식 풀이법이 더 좋을 때도 있다.

- 상향식의 경우 전체 문제의 풀이에 도달하기 전 모든 하위 문제에 대해 계산을 수행해야 한다.

- 하향식의 경우 그럴 필요가 없기에 전체 문제 중 해답을 얻는데 필요한 하위 문제만 풀 수 있다.

 

파스칼의 삼각형에서 특정 위치의 값을 구할 때는

n이 커질 수록 상향식보다는 하향식이 효율적이긴 하다.

 

그러나 저자는 가급적 상향식 접근이 가능하다면 상향식으로 풀 것을 추천한다.