0Pricing
DSA Interview Prep · Pelajaran

Pola DP Interval dan Urutan Pengisian

Definisikan status DP interval dp[i][j], jelaskan mengapa interval harus diisi berdasarkan panjang yang meningkat, dan telusuri polanya pada perkalian rantai matriks

Pola DP Interval dan Urutan Pengisian adalah pelajaran DSA Interview Prep gratis di CoddyKit. Ini adalah pelajaran 1 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar DSA Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus DSA Interview Prep mencakup 4 pelajaran total.

Apa Itu DP Rentang?

DP Rentang adalah pola pemrograman dinamis yang keadaannya dp[i][j] merepresentasikan jawaban optimal untuk submasalah yang mencakup indeks i hingga j. Gagasan utamanya adalah menyelesaikan rentang yang lebih kecil terlebih dahulu, lalu membangun solusi hingga mencakup seluruh rentang. Pola ini secara alami memodelkan masalah seperti perkalian rantai matriks, partisi palindrom, dan pemecahan balon, yang batas submasalahnya merupakan titik ujung kiri dan kanan suatu rentang.

Definisi Keadaan dan Kasus Dasar

Untuk DP Rentang, keadaannya adalah dp[i][j] dengan i <= j. Kasus dasarnya adalah rentang dengan satu elemen: dp[i][i]. Kasus-kasus ini mudah diselesaikan—misalnya, satu matriks memiliki biaya perkalian nol. Rentang dengan dua elemen dp[i][i+1] juga sering memiliki jawaban yang sederhana. Kita mengisi tabel berdasarkan panjang rentang yang meningkat, mulai dari panjang 1 hingga n.

n = 4
dp = [[0] * n for _ in range(n)]
# Base cases: single elements
for i in range(n):
    dp[i][i] = 0  # length-1 intervals

Urutan Pengisian: Panjang Meningkat

Detail penting dalam DP Rentang adalah urutan pengisian. Kita harus menghitung semua rentang dengan panjang L sebelum menghitung rentang dengan panjang L+1, karena rentang yang lebih panjang bergantung pada subrentang yang lebih pendek. Perulangan terluar mengiterasi panjang rentang dari 2 hingga n, perulangan tengah menetapkan batas kiri i, dan kita menentukan batas kanan sebagai j = i + L - 1.

n = 5
dp = [[float('inf')] * n for _ in range(n)]
for i in range(n):
    dp[i][i] = 0

for length in range(2, n + 1):      # interval length
    for i in range(n - length + 1): # left boundary
        j = i + length - 1          # right boundary
        for k in range(i, j):       # split point
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j])

Persiapan Perkalian Rantai Matriks

Masalah klasik DP Rentang adalah perkalian rantai matriks: dengan diberikan matriks berdimensi dims[0..n], temukan jumlah minimum perkalian skalar untuk menghitung hasil perkalian tersebut. Mengalikan matriks A(p×q) dengan B(q×r) memerlukan p*q*r operasi. dp[i][j] = biaya minimum untuk mengalikan matriks i hingga j. Titik pemisah k menentukan lokasi pemisahan urutan menjadi dua subrantai.

def matrix_chain_order(dims):
    n = len(dims) - 1  # number of matrices
    dp = [[0] * n for _ in range(n)]
    
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = float('inf')
            for k in range(i, j):
                cost = dp[i][k] + dp[k+1][j] + dims[i]*dims[k+1]*dims[j+1]
                dp[i][j] = min(dp[i][j], cost)
    return dp[0][n-1]

print(matrix_chain_order([10, 30, 5, 60]))  # 4500

Menelusuri Tabel DP

Mari telusuri contoh rantai matriks dengan dimensi [10, 30, 5, 60] yang merepresentasikan tiga matriks: A(10×30), B(30×5), C(5×60). Untuk dp[0][2], kita mencoba pemisahan pada k=0: dp[0][0] + dp[1][2] + 10×30×60 = 0 + 9000 + 18000 = 27000, dan pada k=1: dp[0][1] + dp[2][2] + 10×5×60 = 1500 + 0 + 3000 = 4500. Jadi, dp[0][2] = 4500, yang dicapai dengan mengalikan AB terlebih dahulu.

Mengapa Urutan Pengisian Ini Berhasil

Saat menghitung dp[i][j], kita merujuk ke dp[i][k] dan dp[k+1][j] untuk semua k dalam [i, j-1]. Kedua subrentang tersebut memiliki panjang yang benar-benar lebih kecil daripada [i, j]. Dengan mengiterasi panjang dari kecil ke besar, semua subrentang yang diperlukan telah dihitung sebelum dibutuhkan. Inilah argumen mendasar tentang kebenaran urutan pengisian DP Rentang—rentang yang lebih pendek selalu menjadi dependensi bagi rentang yang lebih panjang.

DP Rentang dari Atas ke Bawah dengan Memoisasi

DP Rentang juga dapat diimplementasikan dari atas ke bawah dengan memoisation. Kita menulis fungsi rekursif solve(i, j) yang mengembalikan biaya optimal untuk rentang [i, j], lalu menyimpan hasilnya dalam sebuah kamus. Urutan pengisian ditangani secara otomatis oleh rekursi. Pendekatan dari atas ke bawah sering kali lebih mudah dipahami, tetapi dapat menimbulkan beban tambahan pemanggilan fungsi; pendekatan dari bawah ke atas lebih cepat dalam praktik untuk masukan berukuran besar.

from functools import lru_cache

def matrix_chain_memo(dims):
    n = len(dims) - 1
    
    @lru_cache(maxsize=None)
    def solve(i, j):
        if i == j:
            return 0
        return min(
            solve(i, k) + solve(k+1, j) + dims[i]*dims[k+1]*dims[j+1]
            for k in range(i, j)
        )
    
    return solve(0, n-1)

print(matrix_chain_memo([10, 30, 5, 60]))  # 4500

Kompleksitas Waktu dan Ruang

DP Rentang memiliki O(n²) keadaan (semua pasangan (i, j)) dan setiap keadaan mengiterasi O(n) titik pemisah, sehingga menghasilkan O(n³) time secara keseluruhan. Ruang yang digunakan adalah O(n²) untuk tabel DP. Untuk perkalian rantai matriks dengan 100 matriks, jumlahnya adalah 1.000.000 operasi—sangat layak dilakukan. Pola ini muncul dalam banyak masalah LeetCode yang sulit dan menjadi favorit dalam wawancara FAANG karena strukturnya yang tidak langsung terlihat.

Merekonstruksi Solusi Optimal

Untuk merekonstruksi penempatan tanda kurung yang sebenarnya (bukan hanya biayanya), simpan tabel split[i][j] terpisah yang mencatat k mana yang menghasilkan nilai minimum pada setiap keadaan. Kemudian baca pemisahan tersebut secara rekursif: reconstruct(i, j) mencetak pengelompokan optimal dengan melakukan rekursi pada [i, split[i][j]] dan [split[i][j]+1, j]. Teknik ini berlaku untuk semua masalah DP Rentang.

def matrix_chain_with_split(dims):
    n = len(dims) - 1
    dp = [[0]*n for _ in range(n)]
    split = [[0]*n for _ in range(n)]
    
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = float('inf')
            for k in range(i, j):
                cost = dp[i][k] + dp[k+1][j] + dims[i]*dims[k+1]*dims[j+1]
                if cost < dp[i][j]:
                    dp[i][j] = cost
                    split[i][j] = k
    return dp[0][n-1], split

Templat untuk Semua Masalah DP Rentang

Templat DP Rentang universal memiliki tiga bagian: (1) inisialisasi kasus dasar untuk elemen tunggal, (2) lakukan perulangan berdasarkan panjang yang meningkat dan, untuk setiap panjang, lakukan perulangan pada batas kiri yang valid sambil menghitung batas kanan, serta (3) untuk setiap rentang, iterasikan semua titik pemisah dan terapkan rumus rekurensi khusus masalah tersebut. Satu-satunya hal yang berubah di antara masalah adalah rumus rekurensi di dalam perulangan terdalam.

def interval_dp_template(n, base_cost, split_cost):
    dp = [[float('inf')] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = base_cost(i)  # problem-specific base case
    
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            for k in range(i, j):
                # problem-specific recurrence
                candidate = dp[i][k] + dp[k+1][j] + split_cost(i, k, j)
                dp[i][j] = min(dp[i][j], candidate)
    
    return dp[0][n-1]

Masalah DP Rentang yang Umum

Masalah yang menggunakan DP Rentang meliputi: Perkalian Rantai Matriks (meminimalkan operasi), Meletuskan Balon (memaksimalkan koin), Pencetak Aneh (meminimalkan operasi pencetakan), Triangulasi Poligon dengan Skor Minimum, dan Partisi Palindrom II. Masing-masing menggunakan kerangka urutan pengisian yang sama, tetapi dengan rumus rekurensi yang berbeda. Kenali pola ini ketika suatu masalah meminta nilai optimal untuk rentang atau urutan yang dapat dipecah pada titik mana pun di bagian dalamnya.

Uji Cepat

Ujilah pemahaman Anda tentang konsep Struktur Data & Algoritma — Persiapan Wawancara Pemrograman dari pelajaran ini.

Ringkasan Pelajaran

Dalam pelajaran ini Anda telah mempelajari: DP Rentang menggunakan dp[i][j] untuk merepresentasikan jawaban optimal pada suatu rentang, urutan pengisian harus mengikuti panjang rentang yang meningkat agar subrentang dihitung terlebih dahulu, dan templat universalnya memiliki O(n³) time dan ruang O(n²). Berikutnya kita akan mempelajari subsekuens palindromik dan subuntaian palindromik terpanjang menggunakan pola ini.

Pertanyaan yang Sering Diajukan

Apakah pelajaran “Pola DP Interval dan Urutan Pengisian” gratis?

Ya — teks lengkap “Pola DP Interval dan Urutan Pengisian” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus DSA Interview Prep, upgrade ke CoddyKit PRO. Kursus DSA Interview Prep mencakup 4 pelajaran total.

Apa yang akan aku pelajari di “Pola DP Interval dan Urutan Pengisian”?

Definisikan status DP interval dp[i][j], jelaskan mengapa interval harus diisi berdasarkan panjang yang meningkat, dan telusuri polanya pada perkalian rantai matriks Kamu berlatih DSA Interview Prep dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.

Apakah aku perlu pengalaman untuk memulai DSA Interview Prep?

Tidak diperlukan pengalaman sebelumnya. DSA Interview Prep di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 1 dari 4.

Berapa lama pelajaran “Pola DP Interval dan Urutan Pengisian” memakan waktu?

Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.

Bisakah aku menulis dan menjalankan kode dalam pelajaran DSA Interview Prep ini?

Ya. Setiap pelajaran DSA Interview Prep menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.

Semua pelajaran dalam kursus ini

  1. Pola DP Interval dan Urutan Pengisian
  2. Subsekuens dan Substring Palindromik Terpanjang
  3. Partisi Palindrom II
  4. Burst Balloons: DP Interval Terbalik
← Kembali ke DSA Interview Prep