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[..