Pemrograman Dinamis: Contoh, Masalah Umum, dan Solusi

Tidak ada keraguan bahwa masalah pemrograman dinamis bisa sangat menakutkan dalam wawancara pengkodean. Meskipun Anda mungkin mengetahui bahwa suatu masalah perlu diselesaikan menggunakan metode pemrograman dinamis, masih merupakan tantangan untuk dapat menemukan solusi yang berfungsi dalam kerangka waktu yang terbatas.

Cara terbaik untuk menjadi ahli dalam masalah pemrograman dinamis adalah dengan membahasnya sebanyak yang Anda bisa. Meskipun Anda tidak perlu menghafal solusi untuk setiap masalah, ada baiknya Anda memiliki ide tentang cara menerapkannya.

Apa Itu Pemrograman Dinamis?

Sederhananya, pemrograman dinamis adalah metode pengoptimalan untuk algoritma rekursif, yang sebagian besar digunakan untuk menyelesaikan masalah komputasi atau matematika.

Anda juga dapat menyebutnya sebagai teknik algoritmik untuk memecahkan masalah pengoptimalan dengan memecahnya menjadi sub-masalah yang lebih sederhana. Prinsip utama yang mendasari pemrograman dinamis adalah bahwa solusi optimal untuk suatu masalah bergantung pada solusi untuk sub-masalahnya.

Di mana pun kami melihat solusi rekursif yang memiliki panggilan berulang untuk input yang sama, kami dapat mengoptimalkannya menggunakan pemrograman dinamis. Idenya adalah untuk hanya menyimpan hasil subproblem sehingga kita tidak perlu menghitung ulang saat diperlukan nanti.

Solusi yang diprogram secara dinamis memiliki kompleksitas polinomial yang menjamin waktu berjalan yang jauh lebih cepat daripada teknik lain seperti rekursi atau mundur. Dalam kebanyakan kasus, pemrograman dinamis mengurangi kerumitan waktu, yang juga dikenal sebagai besar-O, dari eksponensial ke polinomial.

Apa itu Big-O Notation?

Kode Anda harus efisien, tetapi bagaimana Anda menunjukkan seberapa efisien sesuatu itu? Dengan Big-O!

Sekarang setelah Anda memiliki gambaran yang baik tentang apa itu pemrograman dinamis, sekarang saatnya untuk memeriksa beberapa masalah umum dan solusinya.

Masalah Pemrograman Dinamis

1. Masalah Knapsack

Pernyataan masalah

Diberikan satu set item, masing-masing dengan bobot dan nilai, tentukan jumlah dari setiap item untuk disertakan dalam a koleksi sehingga bobot total tidak melebihi batas yang diberikan dan nilai totalnya sebesar bisa jadi.

Anda diberikan dua array integer nilai [0..n-1] dan bobot [0..n-1] yang mewakili nilai dan bobot masing-masing terkait dengan n item. Juga diberikan adalah bilangan bulat W yang mewakili kapasitas ransel.

Di sini kami memecahkan masalah ransel 0/1, yang berarti kami dapat memilih untuk menambahkan atau mengecualikan item.

Algoritma

• Buat array dua dimensi dengan n + 1 baris dan w + 1 kolom. Nomor baris n menunjukkan kumpulan item dari 1 hingga saya, dan nomor kolom w menunjukkan daya dukung maksimum tas.
• Nilai numerik pada [aku j] menunjukkan nilai total item hingga saya dalam tas yang bisa memuat berat maksimal j.
• Di setiap koordinat [aku j] dalam array, pilih nilai maksimum yang tanpanya bisa kita peroleh item i, atau nilai maksimum yang dapat kita peroleh item imana yang lebih besar.
• Nilai maksimum yang dapat diperoleh dengan memasukkan item i adalah jumlah item saya itu sendiri dan nilai maksimum yang dapat diperoleh dengan sisa kapasitas knapsack.
• Lakukan langkah ini hingga Anda menemukan nilai maksimum untuk file W^th baris.

Kode

def FindMax (W, n, nilai, bobot):
MaxVals = [[0 untuk x dalam rentang (W + 1)] untuk x dalam rentang (n + 1)]
untuk i dalam jangkauan (n + 1):
untuk w dalam rentang (W + 1):
jika i == 0 atau w == 0:
MaxVals [i] [w] = 0
bobot elif [i-1] <= w:
MaxVals [i] [w] = max (nilai [i-1]
+ MaxVals [i-1] [w-weight [i-1]], 
MaxVals [i-1] [w])
lain:
MaxVals [i] [w] = MaxVals [i-1] [w]
mengembalikan MaxVals [n] [W]

2. Masalah Ganti Koin

Pernyataan masalah

Misalkan Anda diberi deretan angka yang mewakili nilai setiap koin. Diberikan jumlah tertentu, temukan jumlah minimum koin yang diperlukan untuk membuat jumlah itu.

Algoritma

• Inisialisasi larik ukuran n + 1, dengan n adalah jumlahnya. Inisialisasi nilai setiap indeks saya dalam array agar sama dengan jumlahnya. Ini menunjukkan jumlah maksimum koin (menggunakan koin denominasi 1) yang dibutuhkan untuk membuat jumlah itu.
• Karena tidak ada denominasi untuk 0, inisialisasi kasus dasar di mana larik [0] = 0.
• Untuk setiap indeks lainnya saya, kami membandingkan nilai di dalamnya (yang awalnya disetel ke n + 1) dengan nilai larik [i-k] +1, dimana k kurang dari saya. Ini pada dasarnya memeriksa seluruh array hingga i-1 untuk menemukan jumlah koin minimum yang dapat kita gunakan.
• Jika nilainya ada larik [i-k] + 1 lebih rendah dari nilai yang ada di larik [i], ganti nilai pada larik [i] dengan yang di larik [i-k] +1.

Kode

def coin_change (d, jumlah, k):
angka = [0] * (jumlah + 1)
untuk j dalam rentang (1, jumlah + 1):
minimum = jumlah
untuk i dalam rentang (1, k + 1):
jika (j> = d [i]):
minimum = min (minimum, 1 + angka [j-d [i]])
angka [j] = minimum
mengembalikan angka [jumlah]

3. Fibonacci

Pernyataan masalah

Seri Fibonacci adalah urutan bilangan bulat di mana bilangan bulat berikutnya dalam rangkaian adalah jumlah dari dua sebelumnya.

Ini ditentukan oleh relasi rekursif berikut: F (0) = 0, F (n) = F (n-1) + F (n-2), dimana F (n) adalah n^th istilah. Dalam soal ini, kita harus menghasilkan semua angka dalam deret Fibonacci hingga n tertentu^th istilah.

Algoritma

• Pertama, gunakan pendekatan rekursif untuk mengimplementasikan relasi perulangan yang diberikan.
• Pemecahan masalah ini secara rekursif memerlukan penguraian F (n) ke F (n-1) + F (n-2), lalu memanggil fungsi dengan F (n-1) dan F (n + 2) sebagai parameter. Kami melakukan ini sampai kasus dasar di mana n = 0, atau n = 1 tercapai.
• Sekarang, kami menggunakan teknik yang disebut memoization. Simpan hasil dari semua pemanggilan fungsi dalam sebuah array. Ini akan memastikan bahwa untuk setiap n, F (n) hanya perlu dihitung satu kali.
• Untuk kalkulasi berikutnya, nilainya dapat diambil dengan mudah dari larik dalam waktu yang konstan.

Kode

def fibonacci (n): 
fibNums = [0, 1] 
untuk i dalam rentang (2, n + 1):
fibNums.append (fibNums [i-1] + fibNums [i-2])
kembali fibNums [n] 

4. Urutan Meningkat Terpanjang

Pernyataan masalah

Temukan panjang pertambahan terpanjang di dalam larik tertentu. Urutan meningkat terpanjang adalah urutan dalam larik angka dengan urutan meningkat. Angka-angka dalam urutan harus unik dan dalam urutan menaik.

Selain itu, item dalam urutan tidak harus berurutan.

Algoritma

• Mulailah dengan pendekatan rekursif di mana Anda menghitung nilai dari peningkatan urutan terpanjang setiap subarray yang mungkin dari indeks nol ke indeks i, di mana i lebih kecil dari atau sama dengan ukuran file Himpunan.
• Untuk mengubah metode ini menjadi metode yang dinamis, buat larik untuk menyimpan nilai untuk setiap urutan. Inisialisasi semua nilai array ini ke 0.
• Setiap indeks saya dari larik ini sesuai dengan panjang urutan peningkatan terpanjang untuk sub larik ukuran saya.
• Sekarang, untuk setiap panggilan rekursif findLIS (arr, n), Periksalah n^th indeks larik. Jika nilai ini 0, maka hitung nilai menggunakan metode pada langkah pertama dan simpan di n^th indeks.
• Terakhir, kembalikan nilai maksimum dari larik. Ini adalah panjang urutan peningkatan terpanjang dari ukuran tertentu n.

Kode

def findLIS (myArray):
n = len (myArray)
lis = [0] * n
untuk i dalam rentang (1, n):
untuk j dalam rentang (0, i):
jika myArray [i]> myArray [j] dan lis [i] lis [i] = lis [j] +1
maxVal = 0
untuk saya dalam rentang (n):
maxVal = max (maxVal, lis [i])
kembalikan maxVal

Solusi untuk Masalah Pemrograman Dinamis

Sekarang Anda telah melalui beberapa masalah pemrograman dinamis yang paling populer, sekarang saatnya untuk mencoba menerapkan solusinya sendiri. Jika Anda mengalami kebuntuan, Anda selalu dapat kembali dan merujuk ke bagian algoritme untuk setiap masalah di atas.

Mengingat betapa populernya teknik seperti rekursi dan pemrograman dinamis saat ini, tidak ada salahnya untuk melihat beberapa platform populer tempat Anda dapat mempelajari konsep dan mengasah keterampilan pengkodean Anda. Meskipun Anda mungkin tidak mengalami masalah ini setiap hari, Anda pasti akan menemukannya dalam wawancara teknis.

Secara alami, memiliki pengetahuan tentang masalah umum pasti akan membuahkan hasil ketika Anda pergi untuk wawancara berikutnya. Jadi bukalah IDE favorit, dan mulai!

9 Saluran YouTube Sepanjang Kode Terbaik untuk Mempelajari Pemrograman

Siap memulai pengkodean? Saluran YouTube ini adalah cara terbaik untuk memulai game, aplikasi, web, dan pengembangan lainnya.

Tentang Penulis