https://blog.naver.com/se2n/223126228252
다이나믹 프로그래밍(DP)
다이나믹 프로그래밍 알고리즘은 부분 문제의 최적해를 이용하여 전체 문제의 최적해를 구하는 알고리즘이다.
- 부분 문제는 전체 문제를 작은 단위로 나눈 문제이다.
- 최적해는 주어진 조건을 만족하는 가장 좋은 해이다.
보통 경우의 수가 너무 많거나 중복적인 연산이 많은 경우 메모이제이션 기법을 활용하여 부분문제의 해결값을 저장 해놓고 저장된 값을 활용하여 더 큰 문제를 해결한다.
다이나믹 프로그래밍 구현 방식
- 부분 문제를 정의한다.
- 부분 문제의 최적해를 구한다.
- 부분 문제의 최적해를 이용하여 전체 문제의 최적해를 구한다.
다이나믹 프로그래밍 사용 기준
- DFS/BFS 로 풀 수 있지만 경우의 수가 너무 많은 문제 (최악의 경우는 직접 반복 계산)
- 경우의 수들에 중복 적인 연산이 많은 경우
다이나믹 프로그래밍 문제
https://won-percent.tistory.com/3
