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.
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.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment