Три лика динамического программирования

Abstract

Работа посвящена некоторым методическим аспектам динамического программирования и решению одной олимпиадной задачи с использованием динамического программирования. Новым является интерпретация метода восходящего динамического программирования в терминах вычисления наименьшей неподвижной точки монотонных функционалов. Такая трактовка позволяет единообразно решать как классические оптимизационные задачи, так и задачи, в которых оптимизационная составляющая не просматривается явно (например, задача синтаксического анализа контекстно-свободных языков алгоритмом Коукера – Янгера – Касами). Она же позволяет унифицировать общую схему динамического программирования в виде шаблона проектирования алгоритмов.

The paper discusses some methodological issues of Dynamic Programming by study of some programming contest problem A methodological novelty consists in treatment (interpretation) of ascending Dynamic Programming as least fixpoint computation (according to Knaster – Tarski fix-point theorem). This interpretation leads to an uniform approach to classical optimization problems as well as to problems where optimality is not explicit (Cocke – Younger – Kasami parsing algorithm for example). This interpretation leads also to an opportunity to design a unified template for imperative Dynamic Programming in a form of algorithm design template.