나한나한나한나

미로에서 한 번 갔던 길을 두 번 가지 않는 것처럼, 프로그램 실행 시에 반복되는(반복될 것이 뻔히 보이는) 동일한 연산을 두 번 하지 않게 해주는 전략이다.

What is DP?

크고 복잡한 main problem을 단순한 subproblems로 잘개 쪼갠 뒤 subproblems의 연산결과를 저장해 둠으로써 redundant 연산을 피하는 일종의 테크닉

• redundant : the state of being not or no longer needed or useful.

How does DP work?

1. Identify Subproblems: main prblem을 더 작고 독립적인 subproblems로 나눈다.
2. Store Solutions: 각 subproblems를 해결하고 그 솔루션을 테이블이나 배열에 저장한다.
3. Build Up Solutions: 저장된 해결책을 사용하여 main prblem의 해결책을 구축한다.
4. Avoid Redundancy: 해결책을 저장함으로써 각 하위 문제를 한 번만 해결하여 계산 시간을 줄인다.

Approaches

Top-down = Memoization ≒ 재귀

Bottom-up = Tabulation ≒ 반복

Examples

• 피보나치 수열
• LCS
• Knapsack Problem