dp.. 개념

dp는 점화식의 정의를 잘 내려야한다
dp의 방식은 top -down, botton -up 방식이 있는데 top - down방식을 쓰면 점화식 조건을 그대로 쓸 수 있는 장점이 있다.
dp는 어떤 것이 dp인가 -> 문제를 나눌때 문제가 겹치는 부분이 있을 수 있다
- 예를 들면 피보나치를 트리 구조로 나타내면 겹치는 부분들이 많다
- 이부분들을 메모이제이션 기법을 적용하면 빠른 시간 내에 구할 수 있다

dp의 시간복잡도 구하기 ->

dp 테이블의 크기(문제의 갯수) * 하나 푸는데 참조하는 부분문제의 갯수이다

kcj3054