목적

• 메모라이제이션을 사용해서 중복을 소거하고, 수행 속도를 개선한다.

조건

• 완전 탐색으로 시간 복잡도가 초과될 때
• 부분 최적해
• 중복 연산

사고 방식

• dp 배열 혹은 자료 구조에 어떤 값을 기록할지 고민
• top - down은 stack overflow를 일으킬 수 있기 때문에, 가급적 지양
• DP는 이전 해를 사용하는 점화식을 작성

기초 문제

• 계단 오르기
• RGB
• 가장 긴 증가하는 부분 수열

[프로그래머스] 정수 삼각형

[프로그래머스] 등굣길