Dynamic Programming

В тази секция ще разгледаме друга много основна тема от състезателното програмиране - динамичното оптимиране. Ще видим как изглежда то в най-базовия му вид - без специфични "чупки" на стейта, които сме покрили по-нататък. Динамичното е начинът да се сведат експоненциални решения до полиномиални такива, без особена промяна в кода. Поради елегантността си те са лесни както за писане от състезател, така и за създаване. В следствие на това те са ужасно често срещани по състезания (може би покриват над 20% от задачите).

Една (относително дълга) тема, която ще ви е нужна за тази секция е Динамично оптимиране, част I. Допълнително четиво, което също би ви било полезно тук е Трикове в динамичното оптимиране.

Задачите в секцията включват едномерно, двумерно, и многомерно динамично. По-сложни динамични задачи с по-разчупен стейт (например битова маска) или по-сложни оптимизации (например със структури данни) ще бъдат разгледани в секциите по-нататък.