Untitled

여러 개의 하위 문제를 먼저 푼 후 그 결과를 쌓아올려 문제를 해결하는 알고리즘

점화식을 찾아서 해결하는 알고리즘 ⇒ 약간 재귀랑 비슷한 느낌이 있지만, 중복된 연산에 대해서 memoization으로 해결해서 더 좋다.

1. 테이블 정의 ⇒ 이것도 쉽지 않다.
2. 점화식 찾기 ⇒ 이것이 젤 중요
3. 초기값 정하기

일반적으로 점화식을 이끌어 내는 것이 쉽지는 않다.

예시 1. 1로 만들기

• 코드

예시 2. 1로 만들기 2

경로 복원용으로 보통 따로 가져 간다.

• 코드

이거 너무 어렵다 인간적으로 풀이가 몇개가 있는거지….

dp 푸는법 찾아보자!!

우선 실버부터 풀어보자