Gesaan dan skop
Kayu tersebut mempunyai titik akhir 0 dan n, dan cuts mengandungi kedudukan dalaman yang berbeza. Pada setiap langkah, pilih satu potongan dalam segmen semasa, bayar panjang segmen tersebut, dan pecahkannya kepada dua segmen. Gunakan skala LeetCode 1547: n paling banyak 1,000,000 dan bilangan potongan m paling banyak 100. Kembalikan hanya kos minimum; memulihkan susunan memerlukan penyimpanan titik keputusan.
Perkara yang diuji oleh penemu duga
- Sama ada anda mengenali DP selang dan bukannya mengikut susunan input secara tamak (greedy).
- Sama ada anda menambah 0 dan n sebagai sentinel serta mengisih kedudukan pemotongan.
- Sama ada anda boleh menerangkan mengapa memilih potongan pertama atau terakhir membahagikan masalah kepada selang-selang yang bebas.
- Sama ada anda boleh menyatakan batas masa, ruang dan keselamatan integer berasaskan m.
Soalan penjelasan
- Bolehkah cuts merangkumi 0, n, atau pendua? Jika ya, adakah API perlu menyahduplikasi atau menolaknya?
- Adakah kita hanya memerlukan kos minimum, atau juga satu susunan optimum? Yang kedua memerlukan jadual pilihan.
- Apakah batas atas untuk m? Nilai m yang lebih besar mungkin menolak masa kubik.
- Adakah setiap kos pemotongan tepat sama dengan panjang segmen semasa? Kos berpemberat mengubah peralihan.
Jawapan 30 saat
Saya mengisih potongan dan menambah 0 dan n. Biarkan dp[i][j] menjadi kos minimum untuk melakukan setiap pemotongan secara ketat antara titik i dan j; titik akhir yang bersebelahan mempunyai nilai sifar. Untuk setiap selang, cuba setiap paksi dalaman k sebagai potongan pertama. Potongan tersebut menelan kos sepanjang selang, dan selang kiri serta kanan adalah bebas, jadi saya menambah dp[i][k] dan dp[k][j]. Mengisi rentang dalam susunan menaik memberikan dp[0][m+1] dalam masa O(m cubed) dan ruang O(m squared).
Jawapan mendalam
1. Tetapkan koordinat dan invarian
Isih cuts dan bina points yang mengandungi 0, semua kedudukan pemotongan, dan n. Selepas pengisihan, potongan dalaman bagi selang dari points[i] ke points[j] adalah tepat indeks antara i dan j. Invarian ini menjadikan keadaan bergantung pada titik akhir dan bukannya sejarah pemotongan sebelumnya.
2. Tentukan keadaan selang
dp[i][j] ialah kos minimum untuk melakukan setiap pemotongan secara ketat di dalam points[i] dan points[j]. Apabila j ialah i tambah satu, tiada pemotongan dalaman, jadi nilainya ialah sifar. Keadaan tidak merekodkan susunan kerana selepas potongan pertama, submasalah kiri dan kanan tidak berinteraksi, dan setiap kos seterusnya hanya bergantung pada segmen semasanya.
3. Terbitkan peralihan
Jika potongan pertama ialah points[k], dengan i kurang daripada k dan k kurang daripada j, bayaran semasa ialah points[j] tolak points[i]. Pemotongan ini menghasilkan dua selang yang bebas:
dp[i][j] = min(
dp[i][k] + dp[k][j] + points[j] - points[i]
for k in (i + 1 ... j - 1)
)Kira rentang yang lebih pendek terlebih dahulu supaya kedua-dua nilai subselang sudah tersedia.
4. Laksanakannya
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. Buktikan peralihan
Gunakan aruhan pada bilangan potongan dalaman. Dengan sifar potongan kosnya adalah sifar. Andaikan selang yang lebih pendek adalah optimum. Setiap susunan optimum mempunyai paksi pertama k. Kosnya ditetapkan sebagai panjang selang penuh; baki kerja terbahagi kepada selang kiri dan kanan, yang nilai optimumnya ialah dp[i][k] dan dp[k][j] mengikut aruhan. Mengambil nilai minimum ke atas setiap k yang mungkin merangkumi setiap potongan pertama, jadi peralihan tersebut adalah optimum.
6. Kerumitan, nombor, dan pembinaan semula
Dengan m potongan dalaman terdapat O(m squared) keadaan dan sehingga O(m) paksi bagi setiap keadaan, menghasilkan masa O(m cubed) dan ruang O(m squared). Dengan n sehingga 1,000,000 dan m paling banyak 100, number JavaScript meliputi julat kos yang dinyatakan; untuk kos berpemberat yang lebih besar, gunakan BigInt atau semakan integer selamat yang jelas. Untuk membina semula susunan, simpan paksi yang mencapai setiap minimum dan pancarkan pokok keputusan secara rekursif.
7. Contoh lawan dan ujian
Untuk n=7 dan cuts=[1,3,4,5], memotong mengikut susunan input menelan kos 20, manakala susunan 3,5,1,4 menelan kos 16. Ini menyangkal pilihan tamak susunan input dan kiri ke kanan. Uji juga satu potongan, kedudukan berhampiran titik akhir, input yang tidak diisih, dasar pendua, jurang berturutan, m maksimum, dan selang asas sifar-potongan-dalaman.
Jawapan model
Saya mengisih potongan dan menambah 0 dan n. dp[i][j] ialah kos minimum untuk setiap pemotongan antara dua titik akhir, dengan sifar untuk titik akhir yang bersebelahan. Bagi setiap selang saya mencuba paksi k sebagai potongan pertama: bayar panjang selang, kemudian tambah kos optimum kiri dan kanan. Mengisi mengikut rentang yang meningkat akan mengembalikan selang luar. Dengan m potongan, kerumitannya ialah masa O(m cubed) dan ruang O(m squared); menyimpan setiap paksi terbaik membina semula susunan. Saya menguji input yang tidak diisih, potongan berhampiran titik akhir, satu potongan, dan contoh lawan n=7, [1,3,4,5].
Kesilapan biasa
- Memotong mengikut susunan input → Susunan tersebut mungkin jauh daripada optimum → Isih dan hitung paksi pertama dengan DP selang.
- Mengabaikan 0 dan n → Panjang sempadan dan keadaan tidak lengkap → Sertakan kedua-dua titik akhir sebagai sentinel.
- Mentakrifkan dp sebagai kos satu potongan sahaja → Pemotongan kemudiannya ditinggalkan → Takrifkannya sebagai kos minimum untuk keseluruhan set dalaman.
- Memilih segmen terpendek atau terpanjang secara tamak (greedy) → Pilihan tempatan mengubah kedua-dua kos submasalah → Tunjukkan pemisahan rekursif dan bukti aruhan.
- Hanya menguji input yang diisih → Kod mungkin secara senyap menganggap susunan sudah betul → Salin dan isih di dalam fungsi, kemudian uji tatasusunan yang tidak diisih.
Soalan susulan
Bagaimanakah anda mengembalikan satu susunan pemotongan optimum?
Simpan paksi yang mencapai setiap minimum selang. Pancarkan paksi tersebut, kemudian lakukan rekursi pada selang kiri dan kanan. Jika beberapa paksi seri, tentukan peraturan deterministik seperti indeks terkecil atau susunan terkecil mengikut leksikografi.
Adakah O(m cubed) boleh diterima apabila m meningkat daripada 100 kepada 2,000?
Jangan berjanji mengenainya tanpa pengukuran. Anggarkan kiraan keadaan dan belanjawan masa, kemudian cari struktur tambahan, penghampiran, atau kekangan luar talian. Tuntutan generik O(m squared) memerlukan sifat kemonotonan atau ketaksamaan segi empat (quadrangle-inequality) yang terbukti.
Bagaimana jika cuts mengandungi kedudukan pendua?
Pemotongan berulang tidak mempunyai kesan fizikal kedua. Isih dan nyahduplikasi, atau tolak pendua mengikut kontrak input; dokumentasikan pilihan tersebut dan ujinya dan bukannya mencipta selang dengan panjang sifar.
Bagaimana jika setiap pemotongan menelan kos sepanjang segmen didarab dengan pemberat?
Jika pemberat hanya bergantung pada paksi k yang dipilih, gantikan sebutan panjang selang dengan panjang selang didarab weight[k], dan pecahan kekal bebas. Jika kos bergantung pada sejarah, kiraan potongan, atau keadaan rentas selang, submasalah tidak lagi bebas dan keadaan mesti direka bentuk semula.