동적 프로그래밍이란?
'Dynamic Programming'에서 'dynamic'은 그냥 말이 멋있어서 붙여진 것으로 알고 있다. 'Dynamic Programming'은 모든 경우의 수를 따져본 후 이를 조합해 최적의 해법을 찾는 방식이다. 주어진 문제를 여러 개의 하위 문제로 나누어 풀고, 하위 문제들의 해결 방법을 결합하여 최종 문제를 해결하는 문제 해결 방식이다. (divide-conquer)
- Dynamic Programming is mainly an optimization over plain recursion. Wherever we see a recursive solution that has repeated calls for same inputs, we can optimize it using Dynamic Programming. The idea is to simply store the results of subproblems, so that we do not have to re-compute them when needed later. This simple optimization reduces time complexities from exponential to polynomial. For example, if we write simple recursive solution for Fibonacci Numbers, we get exponential time complexity and if we optimize it by storing solutions of subproblems, time complexity reduces to linear.
GeeksforGeeks
Boseong