algorithm Dynamic Programming
Introduction
Dynamics programming is a widely used concept and its often used for optimization. It refers to simplifying a complicated problem by breaking it down into simpler sub-problems in a recursive manner usually Bottom up approach. There are two key attributes that a problem must have in order for dynamic programming to be applicable "Optimal substructure" and "Overlapping sub-problems".To achieve its optimization, Dynamics programming uses a concept called Memorization
Remarks
Dynamic Programming is an improvement on Brute Force, see this example to understand how one can obtain a Dynamic Programming solution from Brute Force.
A Dynamic Programming Solution has 2 main requirements:
-
Overlapping Problems
-
Optimal Substructure
Overlapping Subproblems means that results of smaller versions of the problem are reused multiple times in order to arrive at the solution to the original problem
Optimal Substructure means that there is a method of calculating a problem from its subproblems.
A Dynamic Programming Solution has 2 main components, the State and the Transition
The State refers to a subproblem of the original problem.
The Transition is the method to solve a problem based on its subproblems
The time taken by a Dynamic Programming Solution can be calculated as No. of States * Transition Time. Thus if a solution has N^2 states and the transition is O(N), then the solution would take roughly O(N^3) time.
