Question

What is dynamic programming, please explain in detail along with proper example?

Answer 1

If we take a basic view over Dynamic Programming,lets see an example we have a seq of operation like 4+4+4+4+4+4+4+4+4 and ask you to tell me the sum, ans will be 36 and again if I say just add one more +4 to the line and again I ask for sum value then you will just add 36+4 i.e. 40 you just added 4 to the previous solution and didn't counted the whole expression again.So In dynamic programming you don't need to recalculate and it helps in saving time.
Dynamic programming (DP) is a general algorithm design technique for solving problems with overlapping sub-problems.
The key idea is to save answers of overlapping smaller sub-problems to avoid re-computation and properties:
->An instance is solved using the solutions for smaller instances.
->The solutions for a smaller instance might be needed multiple times, so store their results in a table.
->Thus each smaller instance is solved only once.
->Additional space is used to save time.
See this example:follow the link
https://www.topcoder.com/community/data-science/data-science-tutorials/dynamic-programming-from-novice-to-advanced/