Динамично програмиране: примери, често срещани проблеми и решения

Няма съмнение, че проблемите с динамичното програмиране могат да бъдат много смущаващи в интервю за кодиране. Дори когато може да знаете, че проблемът трябва да бъде решен с помощта на метод за динамично програмиране, предизвикателство е да можете да излезете с работещо решение за ограничен период от време.

Най-добрият начин да бъдете добри в проблемите на динамичното програмиране е да преминете през колкото се може повече от тях. Въпреки че не е задължително да запомните решението на всеки проблем, добре е да имате идея как да започнете да го прилагате.

Какво е динамично програмиране?

Най-просто казано, динамичното програмиране е метод за оптимизация на рекурсивни алгоритми, повечето от които се използват за решаване на изчислителни или математически задачи.

Можете също така да го наречете алгоритмична техника за решаване на оптимизационен проблем, като го разбиете на по-прости подзадачи. Основен принцип, на който се основава динамичното програмиране, е, че оптималното решение на даден проблем зависи от решенията на неговите подпроблеми.

Където и да виждаме рекурсивно решение, което има повтарящи се обаждания за едни и същи входове, можем да го оптимизираме с помощта на динамично програмиране. Идеята е просто да съхраняваме резултатите от подпроблеми, така че да не се налага да ги преизчисляваме, когато е необходимо по-късно.

Динамично програмираните решения имат полиномна сложност, която осигурява много по-бързо време на работа от други техники като рекурсия или обратно проследяване. В повечето случаи динамичното програмиране намалява сложността във времето, известна още като голям-О, от експоненциално към полином.

Какво е Big-O Notation?

Вашият код трябва да бъде ефективен, но как да покажете колко ефективно е нещо? С Big-O!

Сега, когато имате добра представа за това какво е динамично програмиране, е време да проверите няколко често срещани проблема и техните решения.

Проблеми с динамичното програмиране

1. Проблем с раницата

Декларация за проблема

Като се има предвид набор от елементи, всеки с тегло и стойност, определете броя на всеки елемент, който да се включи в събиране, така че общото тегло да не надвишава дадена граница и общата стойност да е колкото възможен.

Дадени са ви два целочислени масива стойности [0..n-1] и тежести [0..n-1] които представляват съответно стойности и тегла, свързани с n елемента. Също така е дадено цяло число W което представлява капацитета на раницата.

Тук решаваме проблема с раницата 0/1, което означава, че можем да изберем или да добавим елемент, или да го изключим.

Алгоритъм

• Създайте двуизмерен масив с n + 1 редове и w + 1 колони. Номер на ред н обозначава съвкупността от елементи от 1 до iи номер на колона w обозначава максималната товароносимост на чантата.
• Числовата стойност при [i] [j] обозначава общата стойност на артикулите до i в чанта, която може да носи максимално тегло j.
• На всяка координата [i] [j] в масива изберете максималната стойност, без която можем да получим т. i, или максималната стойност, с която можем да получим т. iкоето е по-голямо.
• Максималната получена стойност чрез включване на елемент i е сумата на артикула i самата и максималната стойност, която може да се получи с оставащия капацитет на раницата.
• Изпълнете тази стъпка, докато намерите максималната стойност за W^ти ред.

Код

def FindMax (W, n, стойности, тегла):
MaxVals = [[0 за х в обхват (W + 1)] за х в обхват (n + 1)]
за i в обхват (n + 1):
за w в обхват (W + 1):
ако i == 0 или w == 0:
MaxVals [i] [w] = 0
elif тежести [i-1] <= w:
MaxVals [i] [w] = max (стойности [i-1]
+ MaxVals [i-1] [w-тегла [i-1]], 
MaxVals [i-1] [w])
друго:
MaxVals [i] [w] = MaxVals [i-1] [w]
връща MaxVals [n] [W]

2. Проблем с промяна на монети

Декларация за проблема

Да предположим, че ви е даден масив от числа, които представляват стойностите на всяка монета. Като се има предвид конкретна сума, намерете минималния брой монети, които са необходими, за да се направи тази сума.

Алгоритъм

• Инициализирайте масив с размер n + 1, където n е сумата. Инициализирайте стойността на всеки индекс i в масива да бъде равна на сумата. Това означава максималният брой монети (използвайки монети от деноминация 1), необходими за съставяне на тази сума.
• Тъй като няма деноминация за 0, инициализирайте основния случай където масив [0] = 0.
• За всеки друг индекс i, сравняваме стойността в него (която първоначално е зададена на n + 1) със стойността масив [i-k] +1, където к е по-малко от i. Това по същество проверява целия масив до i-1, за да намери минимално възможния брой монети, които можем да използваме.
• Ако стойността при която и да е масив [i-k] + 1 е по-малка от съществуващата стойност при масив [i], заменете стойността на масив [i] с този при масив [i-k] +1.

Код

def coin_change (d, сума, k):
числа = [0] * (сума + 1)
за j в диапазон (1, количество + 1):
минимум = сума
за i в обхват (1, k + 1):
ако (j> = d [i]):
минимум = мин (минимум, 1 + числа [j-d [i]])
числа [j] = минимум
върнати номера [сума]

3. Фибоначи

Декларация за проблема

Поредицата на Фибоначи е последователност от цели числа, където следващото цяло число от поредицата е сумата от предишните две.

Определя се от следната рекурсивна връзка: F (0) = 0, F (n) = F (n-1) + F (n-2), където F (n) е n^ти срок. В този проблем трябва да генерираме всички числа в последователност на Фибоначи до дадено n^ти срок.

Алгоритъм

• Първо, използвайте рекурсивен подход, за да приложите дадената рекуррентна връзка.
• Рекурсивното решаване на този проблем води до разрушаване F (n) в F (n-1) + F (n-2)и след това извикване на функцията с F (n-1) и F (n + 2) като параметри. Правим това до основните случаи, когато n = 0, или n = 1 са достигнати.
• Сега използваме техника, наречена запомняне. Съхранявайте резултатите от всички извиквания на функции в масив. Това ще гарантира, че за всеки n, F (n) трябва да се изчисли само веднъж.
• За всички следващи изчисления стойността му може просто да бъде извлечена от масива за постоянно време.

Код

def fibonacci (n): 
fibNums = [0, 1] 
за i в обхват (2, n + 1):
fibNums.append (fibNums [i-1] + fibNums [i-2])
връща fibNums [n] 

4. Най-дълго нарастваща последователност

Декларация за проблема

Намерете дължината на най-дълго нарастващата подпоследователност в даден масив. Най-дълго нарастващата подпоследователност е подпоследователност в масив от числа с нарастващ ред. Числата в подпоследователността трябва да бъдат уникални и във възходящ ред.

Също така не е необходимо елементите от последователността да бъдат последователни.

Алгоритъм

• Започнете с рекурсивен подход, при който изчислявате стойността на най-дългата нарастваща подпоследователност на всеки възможен подмасив от индекс нула до индекс i, където i е по-малък или равен на размера на масив.
• За да превърнете този метод в динамичен, създайте масив, който да съхранява стойността за всяка последователност. Инициализирайте всички стойности на този масив до 0.
• Всеки индекс i на този масив съответства на дължината на най-дълго нарастващата подпоследователност за подмасив с размер i.
• Сега, за всеки рекурсивен разговор на findLIS (arr, n), проверете н^ти индекс на масива. Ако тази стойност е 0, изчислете стойността с помощта на метода в първата стъпка и я съхранявайте в н^ти индекс.
• И накрая, върнете максималната стойност от масива. Това е дължината на най-дълго нарастващата подпоследователност от даден размер н.

Код

def findLIS (myArray):
n = len (myArray)
lis = [0] * n
за i в обхват (1, n):
за j в диапазон (0, i):
ако myArray [i]> myArray [j] и lis [i] lis [i] = lis [j] +1
maxVal = 0
за i в обхват (n):
maxVal = max (maxVal, lis [i])
върнете maxVal

Решения за проблеми с динамичното програмиране

След като вече сте преминали през някои от най-популярните проблеми с динамичното програмиране, е време да опитате да внедрите решенията сами. Ако сте заседнали, винаги можете да се върнете и да се обърнете към раздела за алгоритъма за всеки проблем по-горе.

Като се има предвид колко популярни са техниките като рекурсия и динамично програмиране днес, няма да навреди да разгледате някои популярни платформи, където можете да научите такива концепции и усъвършенствайте уменията си за кодиране. Въпреки че може да не се сблъсквате с тези проблеми ежедневно, със сигурност ще се сблъскате с тях в техническо интервю.

Естествено, притежаването на ноу-хау на често срещани проблеми задължително ще носи дивиденти, когато отидете на следващото си интервю. Така че отворете своя любима IDEи започнете!

9-те най-добри канали в YouTube за програмиране, за да се научите

Готови ли сте да започнете да кодирате? Тези канали в YouTube са чудесен начин да започнете да разработвате игри, приложения, уеб и други.

За автора