<aside> ❓ 동적계획법이란, 작은 문제들을 풀면서 그 결과를 저장해 나아가 전체 문제를 해결하는 알고리즘이다.

</aside>

→ 중복된 계산을 줄여서 계산 속도를 높일 수 있다.

**** 동적 계획법 구현 단계 ****

1. 문제를 하위 문제로 쪼갠다.
2. 하위 문제를 재귀적으로 해결한다.
3. 결과를 저장한다. → Memoziation : 결과값의 유무를 확인하고 계산 수행 (주로 HashMap)
4. 저장된 결과를 이용해 큰 문제를 해결한다.

동적 계획법 조건

동적 계획법을 사용하려면 다음의 조건을 만족해야 한다.

• 최적 부분 구조(Optimal Substructure)

  : 큰 문제의 최적해가 작은 문제의 최적해를 포함하는 성질

• 중복 부분 문제(Overlapping Subproblems)

  : 동일한 작은 문제를 반복적으로 해결해야 하는 성질

동적 계획법 종류

• 탑다운(Top-Down) 방식 - 큰 문제를 해결하기 위해 작은 문제 호출

  → 재귀적을 호출

• 바텀업(Bottom-up) 방식 - 작은 문제부터 차례대로 해결

  → 반복문으로 해결

⭐Dynamic Programming in Programmers

프로그래머스에 있는 DP 문제들

N으로 표현

정수 삼각형

등굣길

사친연산

도둑질