Dynaaminen ohjelmointi saattaa olla useimpien ohjelmistosuunnittelijoiden kirous. En usko, että on olemassa mitään aihetta, josta olen saanut enemmän kysymyksiä.
Ja ymmärrän sen täysin.
Haastattelijat rakastavat kysyä näitä kysymyksiä, koska ne ovat vaikeita.
Haastateltavat todella kamppailevat, koska heillä ei ole ongelmanratkaisukehystä, jonka avulla he voisivat lähestyä dynaamisen ohjelmoinnin ongelmia.
Tämä tarkoittaa, että joka kerta, kun yrität ratkaista dynaamisen ohjelmoinnin ongelmaa, aloitat alusta. Et voi soveltaa malleja, jotka olet nähnyt muissa DP-ongelmissa, koska ne näyttävät täysin erilaisilta. Aloitat siis aina alusta ja yrität ratkaista nämä vaikeat ongelmat tyhjästä.
Tässä postauksessa haluan näyttää sinulle paremman tavan.
Seuraavilla videoilla käydään läpi 6 yleisintä DP-ongelmaa, joita voit odottaa näkeväsi haastatteluissa. Jos opit nämä ongelmat ja opit soveltamaan FAST-menetelmää, olet erittäin hyvässä kunnossa selviytyäksesi dynaamisesta ohjelmoinnista haastatteluissa.
Vinkki: Jos dynaaminen ohjelmointi on sinulle vielä uutta, tutustu ensin ilmaiseen 42-sivuiseen e-kirjaamme Dynaaminen ohjelmointi haastatteluja varten
Katso ongelmat:
Pienin vaihtorahasumma
Kirjoita funktio, jolla voit määrittää pienimmän kolikkomäärän, joka tarvitaan kyseisen vaihtorahasumman aikaansaamiseksi.
Esim. (amerikkalaisia kolikoita käyttäen)
|
1
2
3
4
|
change(1) = 1
change(3) = 3
change(7) = 3
change(32) = 4
|
Longest Common Substring
Voidaan antaa kaksi merkkijonoa, Kirjoita funktio, joka palauttaa pisimmän yhteisen osajonon.
eg.
longestSubstring("ABAB", "BABA") = "ABA"
Fibonacci-luku
Aseta kokonaisluku n ja kirjoita funktio, joka laskee n:nnen Fibonacci-luvun.
Esim.
fibonacci(1) = 1fibonacci(5) = 5fibonacci(10) = 55
Neliöllinen alimatriisi
Gedessä 2D-matriisi, joka koostuu 1:stä ja 0:sta, etsi suurin neliöllinen alimatriisi, joka koostuu kaikista 1:stä.
Esim.
Matriisituotos
Annetaan matriisi, etsi polku vasemmalta ylhäältä oikealle alhaalta alhaalle, jonka produkti on suurin, liikkumalla vain alas ja oikealle.
eg.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
1 -> 4 -> 7 -> 8 -> 9
2016
-1 -> 4 -> 5 -> -6 -> 9
1080
|
0-1 Reppu
Annetaan lista esineitä arvoilla ja painoilla, sekä maksimipaino, etsi maksimiarvo, jonka voit tuottaa kohteista, joiden painojen summa on pienempi kuin maksimiarvo.
eg.
|
1
2
3
|
items = {(w:1, v:6), (w:2, v:10), (w:3, v:12)}
maxWeight = 5
knapsack(items, maxWeight) = 22
|