Understanding Dynamic Programming

Understanding Dynamic Programming

95570 People Read – 1463 People Liked – You Can Also Like

This is an introduction to Dynamic Programming. It is an extensively used concept when solving problems for competitive programming and interviews.

Dynamic Programming involves taking a recursive approach to problem solving and then memoizing subproblem solutions. This works for a class of problems having the following properties:

1) Recursive
2) Optimal Substructure
3) Overlapping Subproblems
4) Memoizable
5) State Space is a Directed Acyclic Graph

These problems are solved by using either a top-down or a bottom-up approach. The Top Down approach uses memoization to avoid recomputing the overlapping subproblems. The bottom up approach is usually faster as it uses precomputed solutions to build a larger solution.

You will often find Dynamic Programming in interview and competitive programming questions. They usually rely more on intuition and mathematical clarity than deep knowledge of data structures.

References:
Introduction to Algorithms – Cormen
http://www.geeksforgeeks.org/dynamic-programming-set-1/
http://www.geeksforgeeks.org/dynamic-programming-set-2-optimal-substructure-property/

#dynamic-programming #competitive-programming #coding-contest

Youtube

Make Beautify

Understanding Dynamic Programming