5.6 Dynamic Programming.

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 ( DP ) is simply the method Divide And Conquer .What is special is that the retroactive formula is used to abort all the solutions that are candidates,but do not have a chance in giving a best solution.Furthermore the information about the choices who still have a possibility of leading to a best solution are stored,and can be used.

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 A and C must go through other points,which means that the choice of the minimum route must be done among the AB(1)C, AB(2)C,...., AB(k)C.

Every route AB(i)C is divided in two parts:the AB(i) and the B(i)C,which must also go through other points.The choice of the minimum route from A to B(i) (sub-problem) can be done through a lot of routes,the same goes for the sub-problem of the minimum route from B(i) to C.It is easily understood that:

Minimum route from A to C= {minimum route from A to B(i) + minimum route from B(i) to C} depending on i.

In a simple and restricted form,the principal of the best can be strictly defined and proofed as in the theorem below.We assume that all the pointers belong to a set ,and that A+B means the set which consists of all the possible sums a+b with a belonging to the A set and b belonging to the B set.
Click to see the theoretical proofing of the above theorem Theorem 5.6-1 .

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

1. The systematic appliance of the " principal of the best " ,so that in every step more and more choices are rejected,and only the ones that offer best solutions to the sub-problems remain.
2. 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