This is an optimization method developed by Richard Bellmann.
Advantages with dynamic programming:
· Reduction in time complexity
· Reduction in call stack of recursive functions
· Avoiding computation of sub-problems if occurring more than once
This concept not only used in computer programming but also in mathematical optimization methods.
Dynamic programming is a concept of divide and reuse for problem solving. Dividing a problem into multiple sub problems, store those solutions and reuse those solutions whenever required to solve the main problem.
This concept is not a generic concept, cannot be applied to all problems. It can only be applied to specific problems where the problem can be divided into multiple sub-problems and solving of sub-problem may occur more than once in a recursive manner.
Dynamic programming can be depicted for below example:
To solve problem P, solve S1, S2, S3 sub problems:
· To solve S1, solve X1, X2, … Xl
· To solve S2, solve X1, X2, …Xm
· To solve S3, solve X1, X2, … Xn
Where some of the sub-problems (X1, X2, .. Xk) are repeated which can be avoided when storing and using their solutions.
Some examples of dynamic programming problems:
· Fibonacci numbers
· Longest common subsequence
· Knapsack problem
· Levenshtein distance problem
· Word break problem
Can you please comment where the dynamic programming cannot be used for some recursive problems? Please specify problems and reasons.
