[TIL]Day 142

동적계획법

주어진 최적화 문제를
재귀적인 방식으로 보다 작은 부분 문제로 나누어
부분 문제를 풀어, 이 해를 조합하여
전체 문제의 답에 이르는 방식

알고리즘의 진행에 따라 탐색해야할 범위를 동적으로 결정함으로써 탐색범위를 한정할 수 있음

동적계획법의 적용 예
피보나치 수열
재귀함수로 구현한다면?
f(4) = f(3)+f(2) = f(2) + f(1) + f(1) + f(0)= f(1) + f(0) + f(1) + f(1) + f(0)

복잡도 지수함수

동적계획법을 적용한다면?
f(0) = 0, f(1) = 1
f(2) = f(1) + f(0) = 1
f(3) = f(2) + f(1) = 2

이런식으로 부분문제의 답을 구해놓고 계산
복잡도 선형함수의 형태

동적계획법을 특징을 잘 보여주는 문제 Knapsack problem