Dynamic Programming

Dynamic programming is a most useful technique, Which are generally used to solve programming problems and provide efficient solution.

Algorithm which are reduced the time complexity of program by using of extra memory. it is called dynamic programming algorithm.

How to detect best dynamic algorithm?

There are following point which is capable to detecting a best dynamic algorithm.

1) Reducing time complexity :

In programming language, We can solve same problem using of different programming algorithms. Such as Greedy algorithm, Divide and conquer, Recursive and iterative algorithms etc.

Dynamic algorithm is a part of existing algorithm which is provides a guarantee to reduce existing time complexity. Which is not possible of common algorithm.

2) Minimum memory space :

This is most important part of dynamic algorithm. Minimal space is used to solve sub-problems so that the result can be used multiple times during program execution. And use of this subproblems are achieve the solution of actual problem. This process are reduced the time complexity and improve program execution speed.

Here mention some programs which is suitable in this criteria.

Word Break Problem 0-1 knapsack problem using dynamic programming Bernoulli's triangle Newman-conway sequence program Subset sum problem using dynamic programming Print Longest common subsequence

Unnecessary dynamic programming solution

This algorithm are use extra memory space but not reduce the time complexity of program. i.e. we can solve the same problem using other algorithm (technique) which provides same complexity and also doesn't use extra space.

Print Ugly Numbers Fibonacci series

Disadvantages of dynamic programming

There are two main disadvantage of dynamic programming.

Complex

This algorithm are complicated because it's need proper planning to memory allocation, subproblem solution, program execution and terminate condition are important and tha is not easy task.

Extra memory

This algorithm are based on extra memory mechanism. Which is not suitable for everyone.