Динамичко програмирање: примери, уобичајени проблеми и решења

Нема сумње да проблеми са динамичким програмирањем могу бити врло застрашујући у интервјуу за кодирање. Чак и када можда знате да проблем треба решити методом динамичког програмирања, изазов је бити у могућности да дођете до радног решења у ограниченом временском оквиру.

Најбољи начин да будете добри у проблемима динамичког програмирања је да прођете кроз што више њих. Иако не морате нужно памтити решење за сваки проблем, добро је имати идеју о томе како кренути у примену.

Шта је динамичко програмирање?

Једноставно речено, динамичко програмирање је метода оптимизације за рекурзивне алгоритме, од којих се већина користи за решавање рачунарских или математичких проблема.

Можете га назвати и алгоритамском техником за решавање проблема оптимизације рашчлањивањем на једноставније под-проблеме. Кључни принцип на којем се заснива динамичко програмирање је да оптимално решење проблема зависи од решења његових под-проблема.

Где год видимо рекурзивно решење које има поновљене позиве за исте улазе, можемо га оптимизовати помоћу динамичког програмирања. Идеја је једноставно похранити резултате потпроблема тако да их касније не морамо поново израчунавати.

Динамички програмирана решења имају полиномску сложеност која осигурава много брже време рада од осталих техника попут рекурзије или повратног праћења. У већини случајева динамичко програмирање смањује временске сложености, такође познате као велики-О, од експоненцијалног до полинома.

Шта је Биг-О нотација?

Ваш код мора бити ефикасан, али како показати колико је нешто ефикасно? Са Биг-О!

Сад кад добро знате шта је динамичко програмирање, време је да погледате неколико уобичајених проблема и њихова решења.

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

1. Кнапсацк Проблем

Изјава о проблему

С обзиром на скуп предмета, сваки са тежином и вредношћу, одредите број сваке ставке коју ћете укључити у сакупљање тако да укупна тежина не пређе дату границу и да укупна вредност буде велика као могуће.

Добили сте два целобројна низа вредности [0..н-1] и тежине [0..н-1] који представљају вредности и тежине повезане са н ставки. Такође је дат цео број В што представља капацитет напртњаче.

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

Алгоритам

• Направите дводимензионални низ помоћу н + 1 редови и в + 1 колоне. Број реда н означава скуп предмета од 1 до и, и број колоне в означава максималну носивост торбе.
• Нумеричка вредност на [и] [ј] означава укупну вредност предмета до и у торби која може да носи максималну тежину ј.
• На свакој координати [и] [ј] у низу одаберите максималну вредност без које можемо добити ставка и, или максималну вредност помоћу које можемо да добијемо ставка икоји је већи.
• Максимална вредност која се може добити укључивањем ставке и је збир јединице и сама и максимална вредност која се може добити са преосталим капацитетом напртњаче.
• Изводите овај корак док не пронађете максималну вредност за В^тх ред.

Код

деф ФиндМак (В, н, вредности, тежине):
МакВалс = [[0 за к у опсегу (В + 1)] за к у опсегу (н + 1)]
за и у опсегу (н + 1):
за опсег в (В + 1):
ако је и == 0 или в == 0:
МакВалс [и] [в] = 0
елиф тегови [и-1] <= в:
МакВалс [и] [в] = мак (вредности [и-1]
+ МакВалс [и-1] [тежине [и-1]], 
МакВалс [и-1] [в])
иначе:
МакВалс [и] [в] = МакВалс [и-1] [в]
повратак МакВалс [н] [В]

2. Проблем промене новца

Изјава о проблему

Претпоставимо да вам је дат низ бројева који представљају вредности сваког новчића. С обзиром на одређену количину, пронађите минималан број кованица потребних за израду тог износа.

Алгоритам

• Иницијализујте низ величине н + 1, где је н износ. Иницијализујте вредност сваког индекса и у низу да буде једнак износу. Ово означава максималан број кованица (користећи кованице апоена 1) потребан да би се сачинио тај износ.
• С обзиром да не постоји деноминација за 0, иницијализујте основни случај где низ [0] = 0.
• За сваки други индекс и, упоређујемо вредност у њему (која је у почетку постављена на н + 1) са вредношћу низ [и-к] +1, где к је мање од и. Ово у основи проверава читав низ до и-1 да би се пронашао најмањи могући број кованица које можемо користити.
• Ако је вредност било која низ [и-к] + 1 је мања од постојеће вредности на низ [и], вредност замените на низ [и] са оним на низ [и-к] +1.

Код

деф цоин_цханге (д, износ, к):
бројеви = [0] * (износ + 1)
за ј у опсегу (1, износ + 1):
минимум = износ
за и у опсегу (1, к + 1):
ако је (ј> = д [и]):
минимум = мин (минимум, 1 + бројеви [ј-д [и]])
бројеви [ј] = минимум
повратни бројеви [износ]

3. Фибонацци

Изјава о проблему

Фибоначијева серија је низ целих бројева, где је следећи цели број у низу збир претходне две.

Дефинисан је следећом рекурзивном релацијом: Ф (0) = 0, Ф (н) = Ф (н-1) + Ф (н-2), где Ф (н) је тада^тх појам. У овом проблему морамо генерисати све бројеве у Фибоначијевој секвенци до датог н^тх појам.

Алгоритам

• Прво, користите рекурзивни приступ да бисте применили дати однос понављања.
• Рекурзивно решавање овог проблема подразумева слом Ф (н) у Ф (н-1) + Ф (н-2), а затим позивање функције помоћу Ф (н-1) и Ж (н + 2) као параметри. То радимо до основних случајева где н = 0, или н = 1 су достигнути.
• Сада користимо технику која се назива памћење. Похраните резултате свих позива функција у низ. Ово ће осигурати да за свако н, Ф (н) потребно је израчунати само једном.
• За било које наредне прорачуне, његова вредност се може једноставно добити из низа у константном времену.

Код

деф фибонацци (н): 
фибНумс = [0, 1] 
за и у опсегу (2, н + 1):
фибНумс.аппенд (фибНумс [и-1] + фибНумс [и-2])
врати фибНумс [н] 

4. Најдуже све веће последице

Изјава о проблему

Пронађите дужину најдуже растуће подсекције унутар датог низа. Најдужа растућа подсеквенца је подредност унутар низа бројева са растућим редоследом. Бројеви унутар подредбе морају бити јединствени и растући.

Такође, ставке низа не морају бити узастопне.

Алгоритам

• Почните са рекурзивним приступом где рачунате вредност најдуже растуће подсекције од сваки могући подниз од индекса нула до индекса и, где је и мања или једнака величини низ.
• Да бисте ову методу претворили у динамичку, створите низ за чување вредности за сваку подсеквенцу. Иницијализујте све вредности овог низа на 0.
• Сваки индекс и овог низа одговара дужини најдуже растуће подсеквенце за подред величине и.
• Сада, за сваки рекурзивни позив од финдЛИС (арр, н), проверите н^тх индекс низа. Ако је ова вредност 0, израчунајте вредност помоћу методе у првом кораку и сачувајте је на н^тх индекс.
• На крају, вратите максималну вредност из низа. Ово је дужина најдуже растуће подсекције дате величине н.

Код

деф финдЛИС (миАрраи):
н = лен (миАрраи)
лис = [0] * н
за и у опсегу (1, н):
за ј у опсегу (0, и):
ако су миАрраи [и]> миАрраи [ј] и лис [и] лис [и] = лис [ј] +1
макВал = 0
за и у опсегу (н):
макВал = мак (макВал, лис [и])
ретурн макВал

Решења за проблеме динамичког програмирања

Сад кад сте прошли неке од најпопуларнијих проблема са динамичким програмирањем, време је да сами покушате да примените решења. Ако заглавите, увек се можете вратити и упутити се на одељак алгоритма за сваки горе наведени проблем.

С обзиром на то колико су данас популарне технике попут рекурзије и динамичког програмирања, неће бити штетно погледати неке популарне платформе на којима можете научити такве концепте и усавршите своје вештине кодирања. Иако можда нећете свакодневно наилазити на ове проблеме, са њима ћете се сигурно сусрести у техничком интервјуу.

Природно, знање о уобичајеним проблемима сигурно ће вам донети дивиденду када одете на следећи интервју. Па отвори свој омиљена ИДЕ, и почните!

9 најбољих ИоуТубе канала за учење код програмирања

Спремни за почетак кодирања? Ови ИоуТубе канали су одличан начин за започињање развоја игара, апликација, веба и другог.

О аутору