Iterative Dynamic Programming

В тази секция ще разгледаме още задачи, решавани с динамично оптимиране. За разлика от миналата секция, в която разгледахме неговите най-базови варианти, тук задачите ще са малко по-специфични - освен да измислите стейта ще трябва да видите и как точно да попълните динамичната таблица, така че да не се налага да я държите цялата в паметта. Това е възможно като се попълва някое от измеренията слой по слой - тоест, ако имате измерение, което зависи единствено от предходния или следващия слой (+/- 1 в индексирането) за изчисляването на текущия. В този случай цялото измерение се свежда до само два слоя, което може да доведе до огромни подобрения в нужната памет (например от N на 2, тоест, например от таблица dyn[N][M][K] на таблица dyn[2][M][K].

Подходяща тема, която можете да разгледате, е Динамично оптимиране, част II.

Задачите в секцията изискват оптимизация на паметта, ползвайки итеративно динамично.