DP : Dynamic Programming : 동적 계획법 : 동적 프로그래밍 : 다이나믹 프로그래밍개념 정리/template/상향식 하향식 비교

Bottom up	Top down
상향식	하향식
for로 구현	재귀함수로 구현
작은 문제를 모아 큰 문제 해결	큰 문제를 해결하기 위해 작은 재귀 함수 호출
점화식 필요	점화식 필요
메모이제이션 없음	메모이제이션=캐싱 결과 저장용 리스트나 사전을 DP 테이블이라 함.
오버헤드를 줄일 수 있다. 일반적으로 성능이 더 좋다.	오버헤드 가능성이 있다.

# 상향식
dp_table[1] = 1
dp_table[2] = 1
for i in range(3, n+1):
    dp_table[i] = dp_table[i - 1] + dp_table[i - 2] # 점화식

# 하향식
def dp(n):
    # 종료조건
    if n == 1:
	return 1
    elif n == 2:
    	return 1

    # 메모이제이션
    if dp_table[n] != 0:
        return dp_table[n]

    # 재귀 호출
    dp_table[n] = dp(n - 1) + dp(n - 2) # 점화식
    return dp_table[n]

• 생각해내기 어렵다면 브루트 포스로 생각하고 그 안에서 중복을 제거한다고 생각해보자

영어지만 자막있는 강의