Dynamic programming with convexity, concavity and sparsity

AbstractDynamic 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