Динамічне програмування

Принцип Беллмана

Оптимальне рішення містить оптимальні підрішення. Важливі властивості: оптимальна підструктура і перекриття підзадач.

Підходи

Мемоізація

Топ-даун рекурсія з кешем результатів.

Табуляція

Боттом-ап заповнення таблиці у відповідному порядку.

Класичні задачі

0/1 рюкзак, необмежений рюкзак.

Редагування рядків (Левенштейн).

Найкоротші шляхи (DAG, Беллман–Форд).

Розбиття, матричне множення, LIS.

Оптимізації

Стиснення пам’яті (1D/rolling arrays).

Монотонні черги, Knuth/QC оптимізації.

Бітсети для підмножин.

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте Spirograph і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.