참고
DP를 사용하는 이유
메모리를 줄여서 중복 연산을 줄이고, 중복 연산을 줄여서 수행 속도를 개선한다.
메모리를 사용한다 -> 자료구조, 배열등을 이용한다.
이전의 연산한 내용을 기억해 두고 다음에 연산이 필요 할때 기억해 둔 값을 사용해서 연산합니다.
DP를 사용하는 경우
DFS/BFS로 풀 수 있지만 경우의 수가 너무 많은 경우
패턴이 500만개 이상일때, 패턴이 1개 추가 될때마다 기하급수적으로 경우의 수가 증가하므로 가능은 하지만 시간이 너무 오래 걸림
경우의 수들에 중복적인 연산이 많은 경우
일일이 모두 한번 씩 중복해서 비교해봤어야 할 조합들이 사전에 미리 최고가 아니면 버려지기 때문에 경우의 수는 급격히 줄어듦
오늘도 내일도 화이팅!