Dinamik Programlama: Örnekler, Yaygın Sorunlar ve Çözümler

Hiç şüphe yok ki dinamik programlama problemleri bir kodlama röportajında ​​çok korkutucu olabilir. Dinamik bir programlama yöntemi kullanılarak bir problemin çözülmesi gerektiğini bilseniz bile, sınırlı bir zaman diliminde çalışan bir çözüm bulabilmek zordur.

Dinamik programlama problemlerinde iyi olmanın en iyi yolu, olabildiğince çok sorunla karşılaşmaktır. Her sorunun çözümünü ezberlemeniz gerekmese de, nasıl uygulanacağı konusunda bir fikrinizin olması iyidir.

Dinamik Programlama Nedir?

Basitçe ifade etmek gerekirse, dinamik programlama, çoğu hesaplama veya matematik problemlerini çözmek için kullanılan yinelemeli algoritmalar için bir optimizasyon yöntemidir.

Bir optimizasyon problemini daha basit alt problemlere bölerek çözmek için buna algoritmik bir teknik de diyebilirsiniz. Dinamik programlamanın dayandığı temel ilke, bir soruna en uygun çözümün, alt sorunlarının çözümlerine bağlı olmasıdır.

Aynı girdiler için tekrarlanan çağrılara sahip özyinelemeli bir çözüm gördüğümüz her yerde, bunu dinamik programlama kullanarak optimize edebiliriz. Buradaki fikir, alt problemlerin sonuçlarını basitçe saklamaktır, böylece daha sonra ihtiyaç duyulduğunda onları yeniden hesaplamak zorunda kalmayız.

Dinamik olarak programlanmış çözümler, özyineleme veya geri izleme gibi diğer tekniklerden çok daha hızlı çalışma süresi sağlayan bir polinom karmaşıklığına sahiptir. Çoğu durumda, dinamik programlama zaman karmaşıklıklarını azaltır. büyük-O, üstelden polinomale.

Big-O Notasyonu nedir?

Kodunuzun verimli olması gerekiyor, ancak bir şeyin ne kadar verimli olduğunu nasıl göstereceksiniz? Big-O ile!

Artık dinamik programlamanın ne olduğu konusunda iyi bir fikriniz olduğuna göre, birkaç yaygın soruna ve bunların çözümlerine göz atmanın zamanı geldi.

Dinamik Programlama Problemleri

1. Sırt Çantası Sorunu

Sorun bildirimi

Her biri bir ağırlık ve bir değere sahip bir dizi öğe verildiğinde, bir toplam ağırlığın belirli bir sınırı aşmaması ve toplam değerin mümkün.

Size iki tamsayı dizisi verilir değerler [0..n-1] ve ağırlıklar [0..n-1] sırasıyla n öğeyle ilişkili değerleri ve ağırlıkları temsil eder. Ayrıca bir tamsayı verilir W sırt çantası kapasitesini temsil eder.

Burada 0/1 sırt çantası sorununu çözüyoruz, bu da bir öğe eklemeyi veya onu hariç tutmayı seçebileceğimiz anlamına gelir.

Algoritma

• İle iki boyutlu bir dizi oluşturun n + 1 satırlar ve w + 1 sütunlar. Bir satır numarası n 1'den benve bir sütun numarası w çantanın maksimum taşıma kapasitesini gösterir.
• Sayısal değer [i] [j] kadar olan öğelerin toplam değerini gösterir ben maksimum j ağırlığı taşıyabilen bir çantada.
• Her koordinatta [i] [j] dizide, olmadan elde edebileceğimiz maksimum değeri seçin öğe iveya elde edebileceğimiz maksimum değer öğe ihangisi daha büyükse.
• İ maddesini dahil ederek elde edilebilecek maksimum değer, maddenin toplamıdır. ben kendisi ve sırt çantasının kalan kapasitesi ile elde edilebilecek maksimum değer.
• İçin maksimum değeri bulana kadar bu adımı gerçekleştirin. W^inci kürek çekmek.

Kod

def FindMax (W, n, değerler, ağırlıklar):
MaksVals = [[aralıktaki x için 0 (W + 1)] aralıktaki x için (n + 1)]
aralıktaki i için (n + 1):
aralıktaki w için (W + 1):
i == 0 veya w == 0 ise:
MaksVals [i] [w] = 0
elif ağırlıkları [i-1] <= w:
MaksDeğerler [i] [w] = maks (değerler [i-1]
+ MaksDeğerler [i-1] [w-ağırlıklar [i-1]], 
MaksVals [i-1] [w])
Başka:
MaksDeğerler [i] [w] = MaksDeğerler [i-1] [w]
MaxVals [n] [W] döndür

2. Para Değiştirme Sorunu

Sorun bildirimi

Her madalyonun değerlerini temsil eden bir sayı dizisi verildiğini varsayalım. Belirli bir miktar verildiğinde, bu miktarı yapmak için gereken minimum jeton sayısını bulun.

Algoritma

• Bir boyut dizisi başlatın n + 1, burada n miktarıdır. Her dizinin değerini başlatın ben dizideki miktara eşit olacak. Bu, bu miktarı telafi etmek için gereken maksimum jeton sayısını (1 değerindeki madeni paraları kullanarak) gösterir.
• 0 için bir mezhep olmadığından, burada temel durumu başlatın dizi [0] = 0.
• Diğer tüm endeksler için ben, içindeki değeri karşılaştırıyoruz (başlangıçta n + 1) değeri ile dizi [i-k] +1, nerede k daha az ben. Bu, kullanabileceğimiz mümkün olan minimum jeton sayısını bulmak için esas olarak i-1'e kadar tüm diziyi kontrol eder.
• Herhangi bir değer varsa dizi [i-k] + 1 mevcut değerden daha az dizi [i], değerini değiştir dizi [i] ile dizi [i-k] +1.

Kod

def coin_change (d, miktar, k):
sayılar = [0] * (miktar + 1)
aralıktaki j için (1, miktar + 1):
minimum = miktar
aralıktaki i için (1, k + 1):
eğer (j> = d [i]):
minimum = minimum (minimum, 1 + sayılar [j-d [i]])
sayılar [j] = minimum
dönüş numaraları [miktar]

3. Fibonacci

Sorun bildirimi

Fibonacci Serisi, serideki bir sonraki tamsayının önceki ikisinin toplamı olduğu bir tamsayı dizisidir.

Aşağıdaki özyinelemeli ilişki ile tanımlanır: F (0) = 0, F (n) = F (n-1) + F (n-2), nerede F (n) n^inci terim. Bu problemde, belirli bir n'ye kadar Fibonacci dizisindeki tüm sayıları üretmeliyiz.^inci terim.

Algoritma

• İlk olarak, verilen yineleme ilişkisini uygulamak için yinelemeli bir yaklaşım kullanın.
• Bu sorunu özyinelemeli olarak çözmek, yıkımı gerektirir. F (n) içine F (n-1) + F (n-2)ve sonra işlevi ile çağırmak F (n-1) ve F (n + 2) parametreler olarak. Bunu temel durumlara kadar yapıyoruz. n = 0veya n = 1 ulaşıldı.
• Şimdi, hafızaya alma adı verilen bir teknik kullanıyoruz. Tüm işlev çağrılarının sonuçlarını bir dizide saklayın. Bu, her n için F (n) yalnızca bir kez hesaplanması gerekir.
• Sonraki hesaplamalar için, değeri diziden sabit zamanda basitçe alınabilir.

Kod

def fibonacci (n): 
fibNums = [0, 1] 
aralıktaki i için (2, n + 1):
fibNums.append (fibNums [i-1] + fibNums [i-2])
dönüş fibNum [n] 

4. En Uzun Süre Artan Sonrası

Sorun bildirimi

Belirli bir dizi içindeki en uzun artan alt dizinin uzunluğunu bulun. En uzun artan alt dizi, artan bir sıraya sahip bir sayı dizisi içindeki bir alt dizidir. Alt dizideki sayılar benzersiz ve artan sırada olmalıdır.

Ayrıca, dizinin öğelerinin ardışık olması gerekmez.

Algoritma

• En uzun artan alt dizinin değerini hesapladığınız yinelemeli bir yaklaşımla başlayın. indeks sıfırdan indeks i'ye olası her alt dizi, burada i'nin boyutundan küçük veya ona eşittir dizi.
• Bu yöntemi dinamik bir yönteme dönüştürmek için, her alt dizinin değerini depolamak için bir dizi oluşturun. Bu dizinin tüm değerlerini 0 olarak başlatın.
• Her indeks ben Bu dizinin sayısı, bir boyut alt dizisi için en uzun artan alt dizinin uzunluğuna karşılık gelir ben.
• Şimdi, her özyinelemeli çağrısı için findLIS (dizi, n), kontrol et n^inci dizinin dizini. Bu değer 0 ise, ilk adımdaki yöntemi kullanarak değeri hesaplayın ve n^inci dizin.
• Son olarak, diziden maksimum değeri döndürün. Bu, belirli bir boyuttaki en uzun artan alt dizinin uzunluğudur n.

Kod

def findLIS (myArray):
n = len (dizim)
lis = [0] * n
aralıktaki i için (1, n):
aralığında j için (0, i):
Dizim [i]> Dizim [j] ve lis [i] lis [i] = lis [j] +1
maxVal = 0
aralıktaki i için (n):
maxVal = max (maxVal, lis [i])
maxVal döndür

Dinamik Programlama Sorunlarına Çözümler

Artık en popüler dinamik programlama problemlerinden bazılarını geçtiğinize göre, çözümleri kendi kendinize uygulamayı denemenin zamanı geldi. Sıkışırsanız, her zaman geri dönebilir ve yukarıdaki her problem için algoritma bölümüne başvurabilirsiniz.

Özyineleme ve dinamik programlama gibi tekniklerin günümüzde ne kadar popüler olduğu düşünüldüğünde, bu tür kavramları öğrenebileceğiniz bazı popüler platformlara göz atmaktan zarar gelmez ve kodlama becerilerinizi geliştirin. Bu sorunlarla günlük olarak karşılaşmasanız da, teknik bir röportajda mutlaka karşılaşacaksınız.

Doğal olarak, ortak problemler hakkındaki bilgi birikimine sahip olmak, bir sonraki mülakata gittiğinizde size fayda sağlayacaktır. Öyleyse aç favori IDEve başlayın!

Programlamayı Öğrenmek için YouTube Kanalları Arasında En İyi 9 Kod

Kodlamaya hazır mısınız? Bu YouTube kanalları oyuna, uygulamaya, web'e ve diğer geliştirmelere başlamak için harika bir yoldur.

Yazar hakkında