DP

DP를 구현하는 방법은 2가지가 존재한다.

	Top-down	Bottom-up
구현	재귀	반복문
저장방식	메모이제이션	타뷸레이션

 

Memoization - 필요한 부분 문제들만 구하기

부분 문제들의 답을 한 번 구했으면 또 구하지 않도록 (중복연산 없도록) cache에 저장해두고 다음에 갖다 쓰기

 

Tabulation - 부분 문제들의 답을 미리 다 구해두면 편하다.

테이블을 채워간다 → 타뷸레이션

 

문제를 쪼개서 작은 문제부터 구해가며 원래 문제의 답을 구하는 방식이다.

핵심은 점화식을 찾고, 테이블만 잘 정의하면 풀린다. (점화식 찾기가 쉽지 않다는게 문제 ㅋㅋ)

 

이제 문제들을 풀어보자.

 

문제풀이

https://koreatstm.tistory.com/148

https://koreatstm.tistory.com/149

https://koreatstm.tistory.com/150

https://koreatstm.tistory.com/151