Dynamic Programming
В тази секция ще разгледаме друга много основна тема от състезателното програмиране - динамичното оптимиране. Ще видим как изглежда то в най-базовия му вид - без специфични "чупки" на стейта, които сме покрили по-нататък. Динамичното е начинът да се сведат експоненциални решения до полиномиални такива, без особена промяна в кода. Поради елегантността си те са лесни както за писане от състезател, така и за създаване. В следствие на това те са ужасно често срещани по състезания (може би покриват над 20% от задачите).Една (относително дълга) тема, която ще ви е нужна за тази секция е Динамично оптимиране, част I. Допълнително четиво, което също би ви било полезно тук е Трикове в динамичното оптимиране.
Задачите в секцията включват едномерно, двумерно, и многомерно динамично. По-сложни динамични задачи с по-разчупен стейт (например битова маска) или по-сложни оптимизации (например със структури данни) ще бъдат разгледани в секциите по-нататък.
Divisor Sequences
93
|
46
Garbage
14
|
20
Caribbean
16
|
14
Triplets
41
|
31
Fibo Primes
22
|
46
Try On
40
|
33
Design Patterns
30
|
43
Ribbons
33
|
24
Meeting
19
|
31
1D Game
26
|
37
Pyramid
18
|
12
Weird Tool
13
|
11
Coprimes - Easy
9
|
31
Coprimes - Hard
14
|
93
Lamps
5
|
3
Knapp
22
|
35
Wine
31
|
30