# data[].attributes.headline
Видео од презентација

# data[].attributes.subject
Видео од презентација

# data[].attributes.headline
Проблем 3.2 - Враќање кусур

# data[].attributes.subject
Проблем 3.2 - Враќање кусур

# data[].attributes.body
⚙️ Дефинирање на состојбата

•Нека dp[i] биде минималниот број на монети потребни за да се добие точно сума i.

🧱 Тривијална состојба

•dp[0] = 0 (за да вратиме кусур од 0 денари, не ни требаат монети)

📌 Преод

•За секоја вредност i од 1 до X, го правиме следново:

dp[i] = минимум од сите dp[i - coin] + 1  за сите монети coin <= i

•Зошто +1? Бидејќи користиме една дополнителна монета (coin) да го добиеме i од i - coin.

✅ Параметар:

•Сумата на пари за која сакаме да најдеме колку најмалку монети ни се потребни за да ја составиме - i.

# data[].attributes.headline
Проблем 3.1 - Враќање кусур

# data[].attributes.subject
Проблем 3.1 - Враќање кусур

# data[].attributes.body
✔ Опис на проблемот:

•Имаме неограничен број на монети со дадени вредности. На пример: coins = {1, 2, 5, 7, 10}

•Сакаме да вратиме кусур од точно X = 19 денари, користејќи најмал можен број на монети.

🧠 Идеја за решавање:

•За секоја сума од 1 до X, пресметуваме колку најмалку монети ни се потребни.

•Го користиме фактот дека веќе сме ги пресметале оптималните решенија за сите помали суми.

•За секоја вредност i, пробуваме да ја додадеме секоја монета и да провериме дали се добива подобро решение.

# data[].attributes.headline
Слајд 11: Важни работи при решавање со динамичко програмирање

# data[].attributes.subject
Слајд 11: Важни работи при решавање со динамичко програмирање

# data[].attributes.body
1. Дефинирање на состојба е подпроблемот што го решаваме. Обично ја запишуваме како dp[i], dp[i][j], итн. Пример во фибоначи проблемот тоа е dp[i] = i-тиот Фибоначи број

2. Избор на параметри што ја дефинираат состојбата. Уствари кои информации се потребни за да го решиш подпроблемот? Пример во Фибоначи зависиме само од i променливата

3. Тривијална состојба се почетните вредности – тие ги знаеме однапред! Што се случува кога i = 0, i = 1, итн. Во Фибоначи знаеме дека fib[1]=1 и fib[2]=1, во примерот со најмал број во низата, ако имаме листа од еден број тој секогаш е најмал. Потребни за да можеме да ја изградиме решението чекор по чекор

4. Трансфер формула со неа преминуваме од познати состојби кон нови. Во Фибоначи беше собирање на двата претходни броја, за најмал број беше барање минимум помеѓу веќе познатиот најмал број и новата вредност што ни следи. Односно како една состојба да ја претставиме преку други подсостојби

5. Чување на резултати во меморија или некоја структура

# data[].attributes.headline
Проблем 2.2 - Фибоначи броеви

# data[].attributes.subject
Проблем 2.2 - Фибоначи броеви

# data[].attributes.body
Решавање одозгора-надолу/top-down: разгледување на поголемите состојби преку објаснување како тие произлегуваат од помалите. На пример, кај рекурзивното решение наведовме дека N-тиот фибоначиев број е збир од (N-1)-виот и (N-2)-риот. Функцијата понатаму ќе продолжи да се повикува и за се помали вредности, се додека не дојдеме до основната состојба, каде знаеме дека првите два фибоначиеви броеви се еднакви на 1.

Решавање одоздола-нагоре/bottom-up: почнувајќи со најмалите состојби, правиме пресметки и ги откриваме вредностите за се поголеми состојби. Кај примерот со фибоначиевите броеви, ова значи дека почнуваме со дефинирање дека првите два фибоначиеви броеви се еднакви на 1. Потоа, ја пресметуваме вредноста на третиот број собирајќи ги првите два. Слично, го откриваме четвртиот број, и така натаму, се додека не дојдеме до N-тиот.

# data[].attributes.headline
Проблем 2.1 - Фибоначи броеви

# data[].attributes.subject
Проблем 2.1 - Фибоначи броеви

# data[].attributes.body
Еве имаме приказ како функционира фибоначи. Гледаме дека фибоначи од 4, 3, 2 и 1 се викаат повеќе пати. Аако бараме фибоначи секвенца од поголем број од 5, ова ќе одземе многу време. Динамичкото програмирање е многу поефикасно за пронаоѓање на фибоначи секвенца зошто се зачувуваат вредностите за секој чекор наместо оддново да се рачуна секој пат.

# data[].attributes.headline
Проблем 1 - Најмал број во низа

# data[].attributes.subject
Проблем 1 - Најмал број во низа

# data[].attributes.body
✔ Опис на проблемот:

•Дадена е низа од цели броеви.

•Потребно е ефикасно да се одговори на прашањето: Кој е најмалиот број од првите X елементи во низата?

🧠 Идеја за решавање:

•Доколку го знаеме најмалиот број до позиција i-1, лесно можеме да го најдеме најмалиот до i.

•Користиме динамичко програмирање за да ги запамтиме решенијата до секоја позиција.

📌 Пример:

Низа: [15, 14, 12, 13, 9, 7, 13, 13, 14, 100]

Најмал од првите 4 елементи: 12

Најмал од првите 9 елементи: 7

Важно е да се запамти тоа што работи само за интервали од првата до х-позиција. Но и за други интервали може да се направи решение со динамичко програмирање, но нема да биде ова. Временска сложеност од O(N) за пресметувањето каде што се пополнува низата, О(1) за одговор на прашањето.

# data[].attributes.headline
Слајд 6: Каде се користи?

# data[].attributes.subject
Слајд 6: Каде се користи?

# data[].attributes.body
Голем дел од технологиите што ги користиме денес, како препораки на Netflix, патеки на Google Maps, па дури и ChatGPT, користат концепти базирани на динамичко програмирање.

# data[].attributes.headline
Слајд 5: Едноставен пример

# data[].attributes.subject
Слајд 5: Едноставен пример

# data[].attributes.body
Треба да собереме 1+1+1+1+1+1+1+1 што е еднакво на 8, ако треба да додадеме уште +1, на 8 ке додадеме 1 што е 9, наспроти скроз одпочеток да ги собираме сите единици.

Кога решаваме покомплексни проблеми – сакаме да го направиме истото.

# data[].attributes.headline
Слајд 4: Една поконкретна дефиниција

# data[].attributes.subject
Слајд 4: Една поконкретна дефиниција

# data[].attributes.body
Што е динамичко програмирање? - Техника за решавање на комплексни проблеми преку:

• Разбивање на проблемот на помали делови (Divide and conquer)

• Решавање на секој мал дел

• Паметење на решенијата (Memoization)

• Комбинирање за финалниот резултат

# data[].attributes.headline
Слајд 3: Примери од вистинскиот свет

# data[].attributes.subject
Слајд 3: Примери од вистинскиот свет

# data[].attributes.body
Ако имаме 10 книги и знаеме дека зборот „херој“ се спомнува вкупно 1000 пати, и некој донесе уште една книга. Колку пати сега се спомнува зборот? Се разбира нема од почеток да ги читаме сите книги и да го броиме одново зборот, само ќе ја прочитаме последната книга и зборовите што сме ги избројале таму, ќе ги додадеме на претходните 1000.

Ова е суштината на динамичкото програмирање – да не го повторуваме тоа што веќе го знаеме, туку да го користиме како дел од новото решение.

# data[].attributes.headline
Слајд 2: Што е динамичко програмирање?

# data[].attributes.subject
Слајд 2: Што е динамичко програмирање?

# data[].attributes.body
Ајде да почнеме со едноставна идеја – дали има смисла повторно да решаваме нешто што веќе сме го решиле? Динамичкото програмирање токму тоа го избегнува.

# data[].attributes.headline
Слајд 1: Вовед

# data[].attributes.subject
Слајд 1: Вовед

# data[].attributes.body
Здраво на сите! Денес ќе зборуваме за еден концепт од алгоритмите кој се вика динамичко програмирање. Иако звучи малку технички или апстрактно, всушност идејата е прилично логична и блиска до тоа како размислуваме во секојдневни ситуации.