PricingLoginStart free
DSA Interview Prep · Pelajaran

Corak DP Selang dan Susunan Pengisian

Takrifkan keadaan DP selang dp[i][j], terangkan sebab selang mesti diisi mengikut susunan panjang yang semakin meningkat, dan jejaki corak itu pada pendaraban rantai matriks.

Pelajaran 1 daripada 413 langkah

Corak DP Selang dan Susunan Pengisian ialah pelajaran DSA Interview Prep percuma di CoddyKit. Ini ialah pelajaran 1 daripada 4. Sebanyak 3 pelajaran dalam laluan pembelajaran ini boleh dibaca sepenuhnya secara percuma — selepas itu, CoddyKit PRO membuka akses kepada semua pelajaran, serta latihan praktikal dengan penyunting kod terbina dalam dan tutor kecerdasan buatan yang tersedia 24/7. Pelajaran ini merupakan sebahagian daripada laluan pembelajaran DSA Interview Prep, dan kemajuan anda disegerakkan merentas web serta aplikasi CoddyKit. Kursus DSA Interview Prep merangkumi sejumlah 4 pelajaran.

Apakah DP Selang

DP selang ialah corak pengaturcaraan dinamik yang keadaan dp[i][j] mewakili jawapan optimum bagi submasalah yang merangkumi indeks i hingga j. Wawasan utama ialah kita menyelesaikan selang yang lebih kecil dahulu dan membina penyelesaian sehingga julat penuh. Corak ini secara semula jadi memodelkan masalah seperti pendaraban rantaian matriks, pembahagian palindrom dan peletusan belon, yang sempadan submasalahnya ialah titik hujung kiri dan kanan sesuatu julat.

Definisi Keadaan dan Kes Asas

Untuk DP selang, keadaan ialah dp[i][j] dengan i <= j. Kes asas ialah selang satu elemen: dp[i][i]. Kes ini mudah diselesaikan — sebagai contoh, satu matriks mempunyai kos pendaraban sifar. Selang dua elemen dp[i][i+1] juga selalunya mempunyai jawapan yang mudah. Kita mengisi jadual mengikut panjang selang yang semakin meningkat, bermula dengan 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

Susunan Pengisian: Panjang Meningkat

Perincian penting dalam DP selang ialah susunan pengisian. Kita mesti mengira semua selang yang panjangnya L sebelum mengira selang yang panjangnya L+1, kerana selang yang lebih panjang bergantung pada subselang yang lebih pendek. Gelung luar mengulangi panjang selang daripada 2 hingga n, gelung tengah menetapkan sempadan kiri i, dan kita mendapatkan sempadan kanan melalui 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])

Persediaan Pendaraban Rantaian Matriks

Masalah DP selang klasik ialah pendaraban rantaian matriks: diberikan matriks dengan dimensi dims[0..n], cari bilangan pendaraban skalar minimum untuk mengira hasil darab tersebut. Pendaraban matriks A(p×q) dengan B(q×r) memerlukan p*q*r operasi. dp[i][j] = kos minimum untuk mendarab matriks i hingga j. Titik split k menentukan tempat urutan dibahagikan kepada dua subrantaian.

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

Menjejaki Jadual DP

Mari kita jejaki contoh rantaian matriks dengan dimensi [10, 30, 5, 60] yang mewakili tiga matriks: A(10×30), B(30×5), C(5×60). Untuk dp[0][2], kita mencuba split 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 mendarab AB terlebih dahulu.

Mengapa Susunan Pengisian Ini Berkesan

Semasa mengira dp[i][j], kita merujuk kepada dp[i][k] dan dp[k+1][j] untuk semua k dalam [i, j-1]. Kedua-dua subselang mempunyai panjang yang lebih kecil secara ketat berbanding [i, j]. Dengan mengulangi panjang daripada kecil kepada besar, semua subselang yang diperlukan telah dikira sebelum kita memerlukannya. Inilah hujah ketepatan asas bagi susunan pengisian DP selang — selang yang lebih pendek sentiasa menjadi kebergantungan bagi selang yang lebih panjang.

DP Selang Atas-Bawah dengan Memoisasi

Sebagai alternatif, DP selang boleh dilaksanakan secara atas-bawah dengan memoizasi. Kita menulis fungsi rekursif solve(i, j) yang mengembalikan kos optimum bagi selang [i, j], lalu menyimpan hasilnya dalam kamus. Susunan pengisian dikendalikan secara automatik oleh rekursi. Pendekatan atas-bawah selalunya lebih mudah difahami, tetapi mungkin mempunyai overhed panggilan fungsi; pendekatan bawah-atas lebih pantas dalam amalan untuk input yang 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

Kerumitan Masa dan Ruang

DP selang mempunyai O(n²) keadaan (semua pasangan (i, j)) dan setiap keadaan mengulangi O(n) titik split, lalu menghasilkan O(n³) time secara keseluruhan. Ruang ialah O(n²) untuk jadual DP. Bagi pendaraban rantaian matriks dengan 100 matriks, ini ialah 1,000,000 operasi — sangat mudah dilaksanakan. Corak ini muncul dalam banyak masalah LeetCode yang sukar dan menjadi kegemaran dalam temu duga FAANG kerana strukturnya yang tidak jelas pada pandangan pertama.

Membina Semula Penyelesaian Optimum

Untuk membina semula pengelompokan berkurungan sebenar (bukan sekadar kos), simpan jadual split[i][j] yang berasingan untuk merekodkan k yang mencapai nilai minimum bagi setiap keadaan. Kemudian baca split secara rekursif: reconstruct(i, j) mencetak pengelompokan optimum dengan melakukan rekursi pada [i, split[i][j]] dan [split[i][j]+1, j]. Teknik ini boleh digunakan untuk semua masalah DP selang.

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 Sebarang Masalah DP Selang

Templat DP selang sejagat mempunyai tiga bahagian: (1) mulakan kes asas untuk elemen tunggal, (2) ulangi panjang yang semakin meningkat dan untuk setiap panjang ulangi semua sempadan kiri yang sah, dengan mengira sempadan kanan, dan (3) bagi setiap selang, ulangi semua titik split serta gunakan rumus rekuren khusus masalah. Satu-satunya perkara yang berubah antara masalah ialah rumus rekuren dalam gelung paling dalam.

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 Selang yang Lazim

Masalah yang menggunakan DP selang termasuk: Pendaraban Rantaian Matriks (minimakan operasi), Peletusan Belon (maksimakan syiling), Pencetak Pelik (minimakan operasi pencetakan), Triangulasi Poligon dengan Skor Minimum dan Pembahagian Palindrom II. Setiap satunya menggunakan rangka susunan pengisian yang sama tetapi rumus rekuren yang berbeza. Kenal pasti corak ini apabila masalah meminta nilai optimum bagi suatu julat atau urutan yang boleh menggunakan split pada mana-mana titik dalaman.

Semakan Pantas

Uji pemahaman anda tentang konsep Struktur Data & Algoritma — Persediaan Temu Duga Pengekodan daripada pelajaran ini.

Jawab dalam pelajaran interaktif

Imbas Kembali Pelajaran

Dalam pelajaran ini anda telah mempelajari: DP selang menggunakan dp[i][j] untuk mewakili jawapan optimum bagi suatu julat, susunan pengisian mesti mengikut panjang selang yang semakin meningkat supaya subselang dikira terlebih dahulu, dan templat sejagat mempunyai O(n³) time dan ruang O(n²). Seterusnya kita akan meneroka subjujukan palindrom terpanjang dan subrentetan palindrom terpanjang menggunakan corak ini.

Percuma untuk bermula

Pelajari Python dengan tutor kecerdasan buatan — percuma

Tulis dan jalankan kod sebenar dalam pelayar anda, dapatkan bantuan segera daripada tutor kecerdasan buatan yang tersedia 24/7, dan sambung semula dari tempat anda berhenti di web atau dalam aplikasi.

Kursus
30
Pelajaran
120
Mula belajar secara percumaLihat kursus penuh

Soalan Lazim

Adakah pelajaran “Corak DP Selang dan Susunan Pengisian” percuma?

Ya — sebanyak 3 pelajaran dalam laluan pembelajaran DSA Interview Prep, termasuk “Corak DP Selang dan Susunan Pengisian”, boleh dibaca sepenuhnya secara percuma di web ini. Selepas itu, CoddyKit PRO membuka akses kepada semua pelajaran, serta latihan interaktif dengan penyunting kod terbina dalam dan tutor kecerdasan buatan yang tersedia 24/7. Kursus DSA Interview Prep merangkumi sejumlah 4 pelajaran.

Apakah yang akan saya pelajari dalam “Corak DP Selang dan Susunan Pengisian”?

Takrifkan keadaan DP selang dp[i][j], terangkan sebab selang mesti diisi mengikut susunan panjang yang semakin meningkat, dan jejaki corak itu pada pendaraban rantai matriks. Anda berlatih DSA Interview Prep menggunakan kod praktikal yang dijalankan terus dalam pelayar, manakala tutor kecerdasan buatan 24/7 menjawab soalan anda semasa anda mengikuti pelajaran.

Adakah saya memerlukan pengalaman untuk memulakan DSA Interview Prep?

Tiada pengalaman terdahulu diperlukan. Pembelajaran DSA Interview Prep di CoddyKit disusun untuk pelajar daripada peringkat pemula hingga lanjutan, jadi anda boleh bermula di sini atau dari awal dan belajar mengikut kadar anda sendiri. Ini ialah pelajaran 1 daripada 4.

Berapa lamakah pelajaran “Corak DP Selang dan Susunan Pengisian” diambil?

Kebanyakan pelajaran CoddyKit mengambil masa kira-kira 5–10 minit. Setiap pelajaran ringkas dan interaktif, jadi anda boleh membuat kemajuan secara berterusan dan menyambung tepat dari tempat anda berhenti di web atau aplikasi.

Bolehkah saya menulis dan menjalankan kod dalam pelajaran DSA Interview Prep ini?

Ya. Setiap pelajaran DSA Interview Prep menyertakan penyunting kod terbina dalam, jadi anda boleh menulis dan menjalankan kod sebenar terus dalam pelayar serta menerima maklum balas kecerdasan buatan serta-merta — tanpa memerlukan persediaan setempat.

Semua pelajaran dalam kursus ini

  1. Corak DP Selang dan Susunan Pengisian
  2. Subjujukan dan Subrentetan Palindrom Terpanjang
  3. Pembahagian Palindrom II
  4. Belon Meletup: DP Selang Songsang
← Kembali ke DSA Interview Prep