Dinamik Programlama veya DP
Bu, Dinamik Programlama (DP) hakkında Teoriden Problemlere kadar zorluk derecesine göre sıralanmış eksiksiz bir eğitimdir.
- DP, karmaşık problemleri daha küçük, örtüşen alt problemlere bölerek çözmek için bilgisayar bilimi ve matematikte kullanılan bir algoritmik tekniktir.
- DP’nin temel fikri, alt problemlerin çözümlerini, her birinin yalnızca bir kez çözüleceği şekilde depolamaktır.
- DP problemlerini çözmek için, öncelikle yineleme ağacında örtüşen alt problemler olacak şekilde yinelemeli bir çözüm yazmalıyız (yinelemeli fonksiyon aynı parametrelerle birden çok kez çağrılır)
- Yinelemeli bir değerin yalnızca bir kez hesaplandığından emin olmak için (algoritmanın harcadığı zamanı iyileştirmek için), yinelemeli çağrıların sonuçlarını saklarız.
- Sonuçları saklamanın iki yolu vardır, biri yukarıdan aşağıya (veya hafızaya alma) ve diğeri aşağıdan yukarıya (veya tablolama).
- DP kullanılarak çözülen bazı popüler problemler şunlardır: Fibonacci Sayıları, Diff Utility ( En Uzun Ortak Alt Dizi ), Bellman-Ford En Kısa Yol , Floyd Warshall , Edit Distance ve Matris Zincir Çarpımı .
Ayrıntılar için lütfen aşağıdaki giriş makalesine bakın.
DP’nin Temelleri
- Dinamik Programlamaya Giriş
- Ezberleme – Eksiksiz bir eğitim
- Tablolama ve Memoizasyon
- Optimum Alt Yapı Özelliği
- Çakışan Alt Problemler Özelliği
- Dinamik Programlama Problemi Nasıl Çözülür?
Konuya Göre Sıralanmış DP Problemleri / Boyutlar / Standart Problemler
- DP Standart Problemleri ve Varyasyonları.
- DP Problemleri Boyutsal Olarak (1D, 2D ve 3D)
- DP Sorunları Konuya Göre
DP Sorunları Zorluk Açısından
DP’de Temel Sorunlar
- Fibonacci sayıları
- Tribonacci Sayıları
- Lucas Sayıları
- Merdiven Çıkma
- 3 Hamleyle Merdiven Çıkma
- Ağırlıklı Tırmanma Merdivenleri
- n’inci Katalan Numarası
- Benzersiz BST’leri say
- Geçerli Parantezleri Say
- Bir Poligonu Üçgenleştirmenin Yolları
- Bir Üçgendeki En Küçük Toplam
- Minimum Mükemmel Kareler
- Bir Kümeyi Bölümlendirmenin Yolları
- Binom Katsayısı
- Pascal Üçgeni
- Pascal Üçgeninin N. Satırı
- Bir Üçgendeki En Küçük Toplam
DP’de Kolay Problemler
- Ev Hırsızı
- Min Maliyet Yolu
- Kod Çözme Yolları
- Altküme Toplam Problemi
- Madeni para değişim problemi – Count Ways
- Madeni Para Değişimi – Toplamı Oluşturmak İçin Minimum Madeni Paralar
- Boyama Çit Algoritması
- Bir Çubuğu Kesmek
- Zıplama Oyunu
- En Uzun Ortak Alt Dize
- Gridlerdeki tüm yolları say
- Engellerle Dolu Bir Izgaradaki Yollar
- K Ters Çevirmeli Permutasyonlar
DP’de Orta Düzey Sorunlar
- En Uzun Ortak Alt Dizi
- En Uzun Artan Alt Dizi
- Mesafeyi Düzenle
- En Büyük Bölünebilir Alt Küme
- Ağırlıklı İş Planlaması
- 0-1 Sırt Çantası Problemi
- 0/1 Sırt Çantasındaki Öğeleri Yazdırma
- Sınırsız Sırt Çantası
- Kelime Kırma Sorunu
- Fayans İstifleme Sorunu
- Kutu-Yığınlama Problemi
- Bölme Sorunu
- En Uzun Palindromik Alt Dizi
- En Uzun Ortak Artan Alt Dizi (LCS + LIS)
- Tüm farklı alt küme (veya alt dizi) toplamları
- Sayım Delilikleri
- Palindromda minimum eklemeler
- Joker Desen Eşleştirme
- Düzenli İfade Eşleştirme
- Farklı tipteki topları yan yana yerleştirin
- 1 bitişik farkla en uzun alt dizi
- Tüm 1’lerden oluşan maksimum boyutlu kare alt matris
- Bellman–Ford Algoritması
- Floyd Warshall Algoritması
DP’de Zor Problemler
- En Büyük X Kenarlı Kare
- Yumurta Düşürme Sorunu
- Palindrom Bölümlendirme
- Palindromik Alt Dize Sayısı
- Kelime Sarma Sorunu
- Bir Oyun İçin En İyi Strateji
- Ressamın bölme problemi
- Köprü ve Torch sorunu için program
- Matris Zincir Çarpımı
- Matris Zincir Çarpımının Yazdırılması
- Maksimum toplam dikdörtgen
- Hisse Senedi Alım ve Satım – En Fazla k Kez
- Hisse Senedi Alım-Satım – En Fazla 2 Kez
- Ters Çevirmeler kullanılarak dizeleri sıralamanın minimum maliyeti
- AP Alt Dizilerinin Sayısı
- Ağaçlardaki DP
- Herhangi bir Düğümün Kök Olabildiği Ağacın Maksimum Yüksekliği
- En uzun tekrar eden ve örtüşmeyen alt dize
- Palindrom Alt Dize Sayısı