다이나믹 프로그래밍 문제 (2, 3) . 3

 

 

 

f(6)의 값은  f(5), f(3), f(2)의 값에서 1을 더한 값과 같다. (대박)
그래서 f(5), f(3), f(2)  이 세개의 값 중 최소를 찾으면 f(6) 값의 최소를 찾을 수 있다.

 

 

 

 

f(1)의 최솟값은 0이기 때문에 DP 배열의 값을 0으로 초기화한다

d[i] = d[i-1] + 1 은 모든 수(i) 에서 적용할 수 있기 때문에 맨 위에 배치

최솟값을 업데이트하는 식으로 해도 문제가 생기지 않는다
제일 작은 수인 '2'부터 각 연산을 적용한 값들을 모두 비교해서 최솟값을 확실하게 찾은 후 다음 수로 넘어가기 때문이다 

 

 

 

 

---

 

 

 

 

 

 

 

 

DP[i-2] 값을 안다면 DP[i] 값도 안다는 것을 의미한다

 

 

 

 

DP[i-2] 값을 만들 수 있다면 DP[i] 값도 만들 수 있다는 의미가 되는 것을 이용한다