Petunjuk dan cakupan
Tongkat memiliki titik ujung 0 dan n, dan cuts berisi posisi internal yang berbeda. Pada setiap langkah, pilih sebuah potongan pada segmen saat ini, bayar panjang segmen tersebut, dan bagi menjadi dua segmen. Gunakan skala LeetCode 1547: n paling banyak 1.000.000 dan jumlah pemotongan m paling banyak 100. Kembalikan hanya biaya minimum; merekonstruksi urutan memerlukan penyimpanan titik keputusan.
Apa yang diuji oleh pewawancara
- Apakah Anda mengenali interval DP alih-alih mengikuti urutan input secara greedy.
- Apakah Anda menambahkan 0 dan n sebagai sentinel dan mengurutkan posisi pemotongan.
- Apakah Anda dapat menjelaskan mengapa memilih potongan pertama atau terakhir membagi masalah menjadi interval-interval independen.
- Apakah Anda dapat menyatakan batas waktu, ruang, dan keamanan bilangan bulat berbasis m.
Pertanyaan klarifikasi
- Bisakah cuts mencakup 0, n, atau duplikat? Jika ya, apakah API harus menghapus duplikat atau menolaknya?
- Apakah kita hanya membutuhkan biaya minimum, atau juga satu urutan optimal? Yang terakhir membutuhkan tabel pilihan.
- Berapa batas atas untuk m? Nilai m yang lebih besar dapat mengesampingkan waktu kubik.
- Apakah setiap biaya pemotongan tepat sebesar panjang segmen saat ini? Biaya berbobot mengubah transisi.
Jawaban 30 detik
Saya mengurutkan potongan dan menambahkan 0 serta n. Misalkan dp[i][j] adalah biaya minimum untuk melakukan setiap pemotongan secara ketat di antara titik i dan j; titik ujung yang bersebelahan memiliki nilai nol. Untuk setiap interval, coba setiap pivot internal k sebagai potongan pertama. Potongan tersebut membutuhkan biaya sebesar panjang interval, dan interval kiri serta kanan bersifat independen, jadi saya menjumlahkan dp[i][k] dan dp[k][j]. Mengisi rentang dalam urutan menaik menghasilkan dp[0][m+1] dalam waktu O(m cubed) dan ruang O(m squared).
Jawaban mendalam
1. Menetapkan koordinat dan invarian
Urutkan cuts dan bangun points yang berisi 0, semua posisi pemotongan, dan n. Setelah pengurutan, potongan internal dari interval dari points[i] ke points[j] tepat berada pada indeks di antara i dan j. Invarian ini membuat state bergantung pada titik ujung alih-alih riwayat pemotongan sebelumnya.
2. Mendefinisikan state interval
dp[i][j] adalah biaya minimum untuk melakukan setiap pemotongan secara ketat di dalam points[i] dan points[j]. Ketika j adalah i ditambah satu, tidak ada potongan internal, sehingga nilainya nol. State tidak mencatat urutan karena setelah potongan pertama, submasalah kiri dan kanan tidak saling berinteraksi, dan setiap biaya berikutnya hanya bergantung pada segmen saat ini.
3. Menurunkan transisi
Jika potongan pertama adalah points[k], dengan i lebih kecil dari k dan k lebih kecil dari j, pembayaran saat ini adalah points[j] dikurangi points[i]. Pemotongan tersebut menciptakan dua interval independen:
dp[i][j] = min(
dp[i][k] + dp[k][j] + points[j] - points[i]
for k in (i + 1 ... j - 1)
)Hitung rentang yang lebih pendek terlebih dahulu sehingga nilai kedua subinterval sudah tersedia.
4. Mengimplementasikannya
function minCost(n: number, cuts: number[]): number {
const points = [0, ...cuts.slice().sort((a, b) => a - b), n];
const m = points.length;
const dp = Array.from({ length: m }, () => Array<number>(m).fill(0));
for (let span = 2; span < m; span += 1) {
for (let left = 0; left + span < m; left += 1) {
const right = left + span;
let best = Number.POSITIVE_INFINITY;
for (let pivot = left + 1; pivot < right; pivot += 1) {
best = Math.min(
best,
dp[left][pivot] + dp[pivot][right] + points[right] - points[left],
);
}
dp[left][right] = best === Number.POSITIVE_INFINITY ? 0 : best;
}
}
return dp[0][m - 1];
}5. Membuktikan transisi
Gunakan induksi pada jumlah potongan internal. Dengan nol potongan, biayanya adalah nol. Asumsikan interval yang lebih pendek adalah optimal. Setiap urutan optimal memiliki pivot pertama k. Biayanya tetap sebesar panjang interval penuh; sisa pekerjaan terbagi menjadi interval kiri dan kanan, yang nilai optimalnya adalah dp[i][k] dan dp[k][j] berdasarkan induksi. Mengambil nilai minimum atas setiap k yang memungkinkan mencakup setiap potongan pertama, sehingga transisi tersebut optimal.
6. Kompleksitas, angka, dan rekonstruksi
Dengan m potongan internal, terdapat O(m squared) state dan hingga O(m) pivot per state, menghasilkan waktu O(m cubed) dan ruang O(m squared). Dengan n hingga 1.000.000 dan m paling banyak 100, number JavaScript mencakup rentang biaya yang ditentukan; untuk biaya berbobot yang lebih besar, gunakan BigInt atau pemeriksaan safe-integer secara eksplisit. Untuk merekonstruksi urutan, simpan pivot yang menghasilkan setiap minimum dan keluarkan pohon keputusan secara rekursif.
7. Contoh sangkalan dan pengujian
Untuk n=7 dan cuts=[1,3,4,5], memotong dalam urutan input membutuhkan biaya 20, sedangkan urutan 3,5,1,4 membutuhkan biaya 16. Ini membantah pilihan greedy berdasarkan urutan input dan dari kiri ke kanan. Uji juga satu potongan, posisi di dekat titik ujung, input yang tidak terurut, kebijakan duplikat, celah berurutan, m maksimum, dan interval dasar tanpa potongan internal.
Jawaban model
Saya mengurutkan potongan dan menambahkan 0 serta n. dp[i][j] adalah biaya minimum untuk setiap pemotongan di antara dua titik ujung, bernilai nol untuk titik ujung yang bersebelahan. Untuk setiap interval saya mencoba pivot k sebagai potongan pertama: bayar panjang interval, lalu tambahkan biaya optimal kiri dan kanan. Mengisi dengan meningkatkan rentang akan mengembalikan interval terluar. Dengan m potongan, kompleksitasnya adalah waktu O(m cubed) dan ruang O(m squared); menyimpan setiap pivot terbaik dapat merekonstruksi urutan. Saya menguji input yang tidak terurut, potongan di dekat titik ujung, potongan tunggal, dan contoh sangkalan n=7, [1,3,4,5].
Kesalahan umum
- Memotong dalam urutan input → Urutan tersebut bisa sangat jauh dari optimal → Urutkan dan hitung pivot pertama dengan interval DP.
- Menghilangkan 0 dan n → Panjang batas dan state menjadi tidak lengkap → Sertakan kedua titik ujung sebagai sentinel.
- Mendefinisikan dp hanya sebagai biaya satu potongan → Potongan berikutnya terabaikan → Definisikan sebagai biaya minimum untuk seluruh himpunan interior.
- Memilih segmen terpendek atau terpanjang secara greedy → Pilihan lokal mengubah biaya kedua submasalah → Tunjukkan pembagian rekursif dan bukti induksi.
- Hanya menguji input yang terurut → Kode mungkin secara diam-diam mengasumsikan urutan → Salin dan urutkan di dalam fungsi, lalu uji dengan array yang tidak terurut.
Pertanyaan lanjutan
Bagaimana cara Anda mengembalikan satu urutan pemotongan yang optimal?
Simpan pivot yang mencapai setiap minimum interval. Keluarkan pivot tersebut, lalu lakukan rekursi pada interval kiri dan kanan. Jika beberapa pivot menghasilkan nilai yang sama, tentukan aturan deterministik seperti indeks terkecil atau urutan terkecil secara leksikografis.
Apakah O(m cubed) dapat diterima ketika m bertambah dari 100 menjadi 2.000?
Jangan menjanjikannya tanpa pengukuran. Perkirakan jumlah state dan batas waktu, lalu cari struktur tambahan, aproksimasi, atau batasan offline. Klaim O(m squared) generik memerlukan sifat monotonisitas atau quadrangle-inequality yang terbukti.
Bagaimana jika cuts berisi posisi duplikat?
Pemotongan berulang tidak memiliki efek fisik kedua. Urutkan dan hapus duplikat, atau tolak duplikat sesuai dengan kontrak input; dokumentasikan pilihan tersebut dan uji daripada membuat interval dengan panjang nol.
Bagaimana jika setiap pemotongan berbiaya panjang segmen dikali bobot?
Jika bobot hanya bergantung pada pivot k yang dipilih, ganti suku panjang interval dengan panjang interval dikali weight[k], dan pembagian tetap independen. Jika biaya bergantung pada riwayat, jumlah potongan, atau state lintas interval, submasalah tidak lagi independen dan state harus dirancang ulang.