Lecture Notes on Dynamic Programming

← Back to document page

Lecture Notes onDynamic Programming15-122: Principles of Imperative ComputationFrank PfenningLecture 23November 16, 20101 IntroductionIn this Lecture we introducedynamic Programming , which is a high-levelcomputational thinking concept rather than a concrete algorithm. Perhapsa more descriptive title for the Lecture would besharing, because dynamicprogramming is about sharing computation. We have already seen earlierthat sharing of space is also crucial: binary decision diagrams in which sub-trees are shared are (in practice) much more efficient than binary decisiontrees in which there is no order to apply Dynamic Programming , we generally look for the fol-lowing optimal solutions to a problem is composed of optimal solutionsto subproblems, there are several optimal solutions, we don t care which one we emphasis on optimality in these conditions dates back to the 1930 swhen Dynamic Programming was developed.

Lecture Notes on Dynamic Programming ... 1 Introduction In this lecture we introduce dynamic ... gramming in the sense of the operations research literature (like ...

  Lecture, Notes, Research, Programming, Operations, Dynamics, Operations research, Lecture notes on dynamic programming