Tinjauan konsep utama
Pelajaran 14 dari 15 dalam kursus Dasar-Dasar Pemrograman Dinamis di Coddy.
Dalam pelajaran ini, kita akan meninjau konsep-konsep utama yang dibahas dalam kursus Dynamic Programming 101.
- Dynamic Programming: Dynamic programming adalah teknik untuk menyelesaikan masalah optimisasi dengan memecahnya menjadi submasalah yang lebih sederhana dan menyelesaikan setiap submasalah hanya sekali.
- Memoization: Memoization adalah teknik untuk menghindari perhitungan berulang dengan menyimpan hasil pemanggilan fungsi yang membutuhkan banyak komputasi dan mengembalikan hasil yang tersimpan dalam cache ketika input yang sama muncul lagi.
- Tabulation: Tabulation adalah teknik untuk menyelesaikan masalah dynamic programming dengan mengisi tabel atau array berisi solusi secara iteratif hingga mendapatkan solusi akhir.
- Optimal substructure: Suatu masalah memiliki struktur optimal jika solusi optimal untuk masalah tersebut mencakup solusi optimal untuk submasalahnya.
- Overlapping subproblems: Suatu masalah memiliki submasalah yang tumpang tindih jika masalah tersebut dapat dipecah menjadi submasalah yang berbagi sub-submasalah.
- Space optimization: Space optimization adalah teknik untuk mengurangi kebutuhan memori algoritma dynamic programming dengan hanya melacak state yang diperlukan.
- Bit masking: Bit masking adalah teknik yang menggunakan manipulasi bit untuk merepresentasikan sekumpulan elemen sebagai bilangan biner.
- Pruning: Pruning adalah teknik untuk mengurangi jumlah komputasi yang diperlukan algoritma dynamic programming dengan menghindari komputasi yang tidak perlu.
Tantangan
SedangTantangan Rekap: jalur dengan biaya minimum
Kamu diberi grid berukuran n x n yang merepresentasikan peta kota. Setiap sel di dalam grid merepresentasikan persimpangan jalan, dan nilai di setiap sel merepresentasikan biaya untuk melewati persimpangan tersebut. Kamu ingin bepergian dari sudut kiri atas grid ke sudut kanan bawah, dan kamu hanya bisa bergerak ke bawah atau ke kanan di setiap persimpangan.
Tulis fungsi min_cost_path(grid) yang menerima grid sebagai input dan mengembalikan biaya minimum untuk melewati grid dari sudut kiri atas ke sudut kanan bawah.
Contohnya:
grid = [
[1, 3, 1],
[1, 5, 1],
[4, 2, 1]
]
min_cost_path(grid) => 7Penjelasan: Jalur dengan biaya minimum adalah 1 -> 3 -> 1 -> 1 -> 1, dengan total biaya 7.
Coba sendiri
def min_cost_path(grid):
# Tulis kodemu di siniSemua pelajaran di Dasar-Dasar Pemrograman Dinamis
3Algoritma pemrograman dinamis
Subsekuens bersama terpanjangMasalah knapsackMasalah penukaran koinJarak editLatihan sendiri: Compiler Python online