Introduction to Dynamic Programming

hi guyz..

Dynamic Programming is easily one of the most crucial topics to master in order to become a good programmer.

In order to effectively take part and achieve in programming competitions, this is one area, we all have to be really gud at, & its pretty simple too, as explained below.

Dynamic programming basically contains 2 elements:

->OPTIMAL SUBSTRUCTURE

a problem exhibits optimal substructure if an optimal solution to the problem contains within it optimal solutions to subproblems. Whenever a problem exhibits optimal substructure, it is a good clue that dynamic programming might apply.

In dynamic programming, we build an optimal solution to the problem from

optimal solutions to subproblems. Consequently, we must take care to ensure that the range of

subproblems we consider, includes those used in an optimal solution

Optimal substructure varies across problem domains in two ways:

1. how many subproblems are used in an optimal solution to the original problem, and

2. how many choices we have in determining which subproblem(s) to use in an optimal

solution.

Dynamic programming uses optimal substructure in a bottom-up fashion. That is, we first find

optimal solutions to subproblems and, having solved the subproblems, we find an optimal

solution to the problem. Finding an optimal solution to the problem entails making a choice

among subproblems as to which we will use in solving the problem. The cost of the problem

solution is usually the subproblem costs plus a cost that is directly attributable to the choice

itself.

-->OVERLAPPING SUBPROBLEMS:

The second ingredient that an optimization problem must have for dynamic programming to

be applicable is that the space of subproblems must be "small" in the sense that a recursive

algorithm for the problem solves the same subproblems over and over, rather than always

generating new subproblems. Typically, the total number of distinct subproblems is a

polynomial in the input size. When a recursive algorithm revisits the same problem over and

over again, we say that the optimization problem has overlapping subproblems

Dynamic-programming algorithms typically take advantage of overlapping subproblems by solving each subproblem once and then storing thesolution in a table where it can be looked up when needed, using constant time per lookup.