DP (Dynamic Programming)

목적

중복 연산을 줄여서 퍼포먼스를 높인다!!

중복해서 연산해야 하는 상황에서, 연산한 결과를 원하는 자료구조에 담아놓고,
해당 자료구조을 활용해서 중복되는 연산을 줄이는 것이 목적이다.

DP로 풀어야 하는 문제

DFS/BFS로 풀 수는 있지만 경우의 수가 너무 많거나 중복되는 경우의 수가 많은 문제
== 중복되고 불필요한 연산을 줄여야 하는 경우!!

문제해결 접근 방법

현재까지의 연산을 기억해놓고 다시 하지 않기 위해서,
자료구조를 선언하고 해당 자료구조에 연산들을 저장해놓고
그 값들을 참조하면서 중복 연산을 줄이는 것에 목적이 있다.

어떤 자료구조에 어떤 정보값을 담아야 하는지가 관건.

많이 풀어보잣

관련 문제

프로그래머스 Lv3 정수 삼각형
프로그래머스 Lv3 등굣길

---

참고

https://youtu.be/0bqfTzpWySY