DEV Community


Posted on

Dynamic programming

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.

Image description

Advantage of dynamic programming:
The advantage of dynamic programming is that it can obtain both local and total optimal solution. Also, practical knowledge can be used to gain the higher efficiency of dynamic programming. However, there is no unifiedstandard model for dynamic programming, multiple condition may appear during the solving process.

disadvantage of dynamic programming:
It takes a lot of memory to store the calculated result of every subproblem without ensuring if the stored value will be utilized or not. Many times, output value gets stored and never gets utilized in the next subproblems while execution.

Discussion (0)