TIL 11월 1일 2023년

동적 프로그래밍을 사용해야 하는지 판단하는 과정

1. 중복계산 : 문제의 구조에서 같은 작은 문제가 여러번 계산되어야 할 가능성이 보인다면 DP가 유용할 수있음.
2. 최적 부분 구조 : 큰 문제의 해답을 작은 문제의 해답으로부터 구성할 수 있는 경우 DP를 고려.
3. 점화식 또는 재귀적 구조 : 점화식이나 재귀적 구조가 보이면 DP를 사용