Dynamic Programming
В тази секция ще разгледаме друга много основна тема от състезателното програмиране - динамичното оптимиране. Ще видим как изглежда то в най-базовия му вид - без специфични "чупки" на стейта, които сме покрили по-нататък. Динамичното е начинът да се сведат експоненциални решения до полиномиални такива, без особена промяна в кода. Поради елегантността си те са лесни както за писане от състезател, така и за създаване. В следствие на това те са ужасно често срещани по състезания (може би покриват над 20% от задачите).Една (относително дълга) тема, която ще ви е нужна за тази секция е Динамично оптимиране, част I. Допълнително четиво, което също би ви било полезно тук е Трикове в динамичното оптимиране.
Задачите в секцията включват едномерно, двумерно, и многомерно динамично. По-сложни динамични задачи с по-разчупен стейт (например битова маска) или по-сложни оптимизации (например със структури данни) ще бъдат разгледани в секциите по-нататък.
Divisor Sequences
103
|
46
Garbage
19
|
20
Caribbean
22
|
17
Triplets
51
|
33
Fibo Primes
28
|
39
Try On
47
|
32
Design Patterns
34
|
42
Ribbons
38
|
25
Meeting
22
|
33
1D Game
32
|
38
Pyramid
25
|
16
Weird Tool
14
|
12
Coprimes - Easy
10
|
32
Coprimes - Hard
14
|
93
Lamps
5
|
3
Knapp
27
|
38
Wine
34
|
31
Increments
5
|
23
Three
3
|
50
Twin Letters
5
|
23