Dynamic Programming Algorithms
programming is a fancy name for using divide-and-conquer technique with a table.
As compared to divide-and-conquer, dynamic programming is more powerful and
subtle design technique. Let me repeat , it is not a specific algorithm, but it is a meta-technique (like
divide-and-conquer). This technique was developed back in the days when
“programming” meant “tabular method” (like linear programming). It does not
really refer to computer programming. Here in our advanced algorithm course, we’ll
think of “programming” as a “tableau method” and certainly not writing code.
Dynamic programming is a stage-wise search method suitable for optimization
problems whose solutions may be viewed as the result of a sequence of decisions.
The most attractive property of this strategy is that during the search for a
solution it avoids full enumeration by pruning early partial decision solutions