The same general problem is faced here,as in the greedy method,that is the quest for a way to calculate the best solution without spending special time or effort for each and every one of the candidate solutions.

Dynamic Programming ( ** DP **) tends to break the original problem to sub-problems and chooses
the best solution in the sub-problems,beginning from the smaller in size.The best solution in the
bigger sub-problems is found by using the best ones of the smaller sub-problems through a
retroactive formula which connects the solutions.Up to this point (

In finding this formula,we make a lot of use,of what is called ** " principal of the best " **,which
roughly defined,says that if the possible solutions of a problem are a combination of possible
solutions of sub-problems,then we must expect that the best solution of the problem will come
by the combination of the best solutions of sub-problems.

A typical example of applying the ** principal of the best **is given by the problem of minimum
routes (also in Chapter 5.7 ) between 2 points:Let's assume that all the possible routes between
two points

Every route ** AB(i)C **is divided in two parts:the

Click to see the theoretical proofing of the

We can now say that the main characteristics of a DP algorithm are:

- The systematic appliance of the
,so that in every step more and more choices are rejected,and only the ones that offer best solutions to the sub-problems remain.*" principal of the best "* - The storing of best solutions in internal steps for future use of them.

A nice example for dynamic programming,is the multiplication of arrays. Click for** ****EXAMPLE
**of the best way to multiply arrays.

HTML PAGE DIRECTOR :Papaioannou Panagiotis