ABSTRACT
This chapter discusses three dynamic programming (DP) experiments, linear dynamic programming, tree-like dynamic programming and dynamic programming with state compression. DP is used to solve optimization problems. DP breaks an optimization problem into a sequence of related subproblems, solves these subproblems just once, stores solutions to subproblems, and constructs an optimal solution to the problem, based on solutions to subproblems. DP is used to calculate all solutions to the problem in the range. Many problems in computer science involve maximizing some measure according to constraints. Consider a history exam in which students are asked to put several historical events into chronological order. Secret agent Maria was sent to Algorithms City to carry out an especially dangerous mission. The input consists of pairs of lines. The first line of a pair contains the first string and the second line contains the second string.
