[Note] Dynamic Programming (동적 프로그래밍)을 알아보자

[saseungmin]

📚 쉽게 배우는 알고리즘 책 Chapter 9: 동적 프로그래밍

• 정리 링크
• 다음 두 상황일 때 DP를 사용하자.

1. 최적 부분 구조를 이룬다.
2. 재귀적으로 구현했을 때 중복 호출로 심각한 비효율이 발생한다.

책에 있는 예제를 공부하고 4가지 예제를 JavaScript로 재귀로 풀어본 뒤 DP로 풀어보았다.

1. 피보나치
2. 행렬 경로
3. 돌 놓기 DP
4. 최장 공통 부분 수열 DP => 백준 9251