[leetCode] D-12. Dynamic Programming(DP)

다이내믹 프로그래밍 (DP)

큰 문제를 작은 문제로 나눠서 푸는 알고리즘

DP를 사용할 수 있는 알고리즘 문제는 두 가지 조건을 충족한다.

1. Overlapping Subproblem

• 큰 문제와 작은 문제를 같은 방법으로 풀 수 있어야 하고, 문제를 작은 문제로 쪼갤 수 있어야 한다.

2. Optimal Substructure

• 문제의 정답을 작은 문제의 정답에서 구할 수 있어야 한다.

구현 방식

• top-down : 재귀함수
• bottom-up : 반복문
  방식이 있다.

Memoization

DP는 나눈 문제들이 중복이 될 수 있으므로 이미 끝낸 계산은 메모해 둔 후 활용하는 것이 효율적이다.

관련 문제 풀이

🖲 D-12

• [leetCode][JS] 70. Climbing Stairs