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