Dynamic programming with convexity, concavity and sparsity
Zvi Galil, Kunsoo Park · Theoretical Computer Science · 1992
Dynamic programming is a general problem-solving technique that has been widely used in various fields such as control theory, operations research, biology and computer science. In many applications dynamic programming problems satisfy additional conditions of convexity, concavity and sparsity. This paper presents a classification of dynamic programming problems and surveys efficient algorithms based on the three conditions.