다이나믹 프로그래밍의 목적
•
문제 해결을 위해 고안됨 → 알고리즘
•
왜 다이나믹 프로그래밍이 필요한가?
◦
수많은 경우의 수를 따져야 하는 과정에서 수행 시간을 단축하고지 만들어진 알고리즘
◦
최단 경로, 최고 점수
•
메모리를 사용해서 중복 연산을 줄이고 중복 연산을 줄여서 수행 속도를 개선
다이나믹 프로그래밍 예제
•
정수 삼각형
다이나믹 프로그래밍 문제 구분하기
•
DFS/BFS로 풀 수는 있지만 경우의 수가 너무 많은 문제
•
경우의 수들에 중복적인 연산이 많은 경우