Rumah pembangunan bahagian belakang tutorial php Kos Minimum untuk Menghubungkan Dua Kumpulan Mata

Kos Minimum untuk Menghubungkan Dua Kumpulan Mata

Sep 01, 2024 am 06:34 AM

1595. Kos Minimum untuk Menghubungkan Dua Kumpulan Mata

Kesukaran: Sukar

Topik: Tatasusunan, Pengaturcaraan Dinamik, Manipulasi Bit, Matriks, Bitmask

Anda diberi dua kumpulan mata di mana kumpulan pertama mempunyai saiz1 mata, kumpulan kedua mempunyai saiz2 mata, dan saiz1 > = saiz2.

Kos sambungan antara mana-mana dua titik diberikan dalam saiz1 x saiz2 matriks dengan kos[i][j] ialah kos penyambungan titik i daripada kumpulan pertama dan titik j kumpulan kedua. Kumpulan disambungkan jika setiap titik dalam kedua-dua kumpulan disambungkan kepada satu atau lebih titik dalam kumpulan bertentangan. Dalam erti kata lain, setiap titik dalam kumpulan pertama mesti disambungkan kepada sekurang-kurangnya satu titik dalam kumpulan kedua dan setiap titik dalam kumpulan kedua mesti disambungkan kepada sekurang-kurangnya satu titik dalam kumpulan pertama.

Pulangan kos minimum yang diperlukan untuk menyambung dua kumpulan.

Contoh 1:

Minimum Cost to Connect Two Groups of Points

  • Input: kos = [[15, 96], [36, 2]]
  • Output: 17
  • Penjelasan: Cara optimum untuk menghubungkan kumpulan ialah:
  1--A
  2--B
  This results in a total cost of 17.

Contoh 2:

Minimum Cost to Connect Two Groups of Points

  • Input: kos = [[1, 3, 5], [4, 1, 1], [1, 5, 3]]
  • Output: 4
  • Penjelasan: Cara optimum untuk menghubungkan kumpulan ialah:
  1--A
  2--B
  2--C
  3--A
  This results in a total cost of 4.

Perhatikan bahawa terdapat berbilang titik disambungkan ke titik 2 dalam kumpulan pertama dan titik A dalam kumpulan kedua. Ini tidak penting kerana tiada had bilangan mata yang boleh disambungkan. Kami hanya mengambil berat tentang jumlah kos minimum.

Contoh 3:

  • Input: kos = [[2, 5, 1], [3, 4, 7], [8, 1, 2], [6, 2, 4], [3, 8, 8] ]
  • Output: 10

Kekangan:

  • saiz1 == kos.panjang
  • saiz2 == kos[i].panjang
  • 1 <= saiz1, saiz2 <= 12
  • saiz1 >= saiz2
  • 0 <= kos[i][j] <= 100

Petunjuk:

  1. Setiap titik di sebelah kiri sama ada akan disambungkan ke titik tepat yang telah disambungkan ke beberapa nod kiri, atau subset nod di sebelah kanan yang tidak disambungkan ke mana-mana nod
  2. Gunakan pengaturcaraan dinamik dengan bitmasking, di mana keadaan akan berada (bilangan mata yang diberikan dalam kumpulan pertama, bitmask mata yang diberikan dalam kumpulan kedua).

Penyelesaian:

Kami boleh memanfaatkan pengaturcaraan dinamik dengan bitmasking. Ideanya adalah untuk meminimumkan kos dengan mempertimbangkan setiap titik dalam kumpulan pertama dan cuba menyambungkannya ke semua titik dalam kumpulan kedua.

Pendekatan Pengaturcaraan Dinamik (DP) dengan Bitmasking

Langkah-langkah:

  1. Perwakilan Negeri:

    • Gunakan dp jadual DP[i][topeng] di mana:
      • i ialah indeks dalam kumpulan pertama (dari 0 hingga saiz1-1).
      • mask ialah bitmask yang mewakili titik mana dalam kumpulan kedua telah disambungkan.
  2. Peralihan Negeri:

    • Untuk setiap titik dalam kumpulan pertama, cuba sambungkannya ke setiap titik dalam kumpulan kedua, kemas kini jadual DP dengan sewajarnya.
    • Jika titik baharu dalam kumpulan kedua disambungkan, kemas kini bit yang sepadan dalam topeng.
  3. Kes Asas:

    • Mulakan dengan dp[0][0] = 0 (tiada sambungan pada mulanya).
  4. Matlamat:

    • Kira kos minimum untuk dp[saiz1][(1 << saiz2) - 1], yang mewakili penyambungan semua titik daripada kedua-dua kumpulan.

Mari laksanakan penyelesaian ini dalam PHP: 1595. Kos Minimum untuk Menghubungkan Dua Kumpulan Mata






Penjelasan:

  • Dp tatasusunan DP[i][mask] menyimpan kos minimum untuk menyambung mata i pertama daripada kumpulan 1 dengan mata dalam kumpulan 2 seperti yang ditunjukkan oleh topeng.
  • Gelung bersarang berulang pada setiap gabungan i dan mask, cuba mencari kos optimum dengan mempertimbangkan semua sambungan yang mungkin.
  • Akhirnya, penyelesaian mengira kos minimum mengambil kira senario di mana beberapa titik dalam kumpulan kedua mungkin masih tidak disambungkan, memastikan semua titik disambungkan.

Pendekatan ini mengendalikan kekangan masalah dengan cekap dan memastikan kos minimum untuk menyambungkan dua kumpulan.

Pautan Kenalan

Jika anda mendapati siri ini membantu, sila pertimbangkan untuk memberi repositori bintang di GitHub atau berkongsi siaran pada rangkaian sosial kegemaran anda ?. Sokongan anda amat bermakna bagi saya!

Jika anda mahukan kandungan yang lebih berguna seperti ini, sila ikuti saya:

  • LinkedIn
  • GitHub

Atas ialah kandungan terperinci Kos Minimum untuk Menghubungkan Dua Kumpulan Mata. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!

Kenyataan Laman Web ini
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn

Alat AI Hot

Undress AI Tool

Undress AI Tool

Gambar buka pakaian secara percuma

Undresser.AI Undress

Undresser.AI Undress

Apl berkuasa AI untuk mencipta foto bogel yang realistik

AI Clothes Remover

AI Clothes Remover

Alat AI dalam talian untuk mengeluarkan pakaian daripada foto.

Clothoff.io

Clothoff.io

Penyingkiran pakaian AI

Video Face Swap

Video Face Swap

Tukar muka dalam mana-mana video dengan mudah menggunakan alat tukar muka AI percuma kami!

Alat panas

Notepad++7.3.1

Notepad++7.3.1

Editor kod yang mudah digunakan dan percuma

SublimeText3 versi Cina

SublimeText3 versi Cina

Versi Cina, sangat mudah digunakan

Hantar Studio 13.0.1

Hantar Studio 13.0.1

Persekitaran pembangunan bersepadu PHP yang berkuasa

Dreamweaver CS6

Dreamweaver CS6

Alat pembangunan web visual

SublimeText3 versi Mac

SublimeText3 versi Mac

Perisian penyuntingan kod peringkat Tuhan (SublimeText3)

Topik panas

Tutorial PHP
1535
276
PHP memanggil AI Pembantu Suara Pintar PHP Pembinaan Sistem Interaksi Suara PHP PHP memanggil AI Pembantu Suara Pintar PHP Pembinaan Sistem Interaksi Suara PHP Jul 25, 2025 pm 08:45 PM

Input suara pengguna ditangkap dan dihantar ke backend PHP melalui API Mediarecorder JavaScript front-end; 2. PHP menjimatkan audio sebagai fail sementara dan memanggil STTAPI (seperti Pengiktirafan Suara Google atau Baidu) untuk mengubahnya menjadi teks; 3. PHP menghantar teks kepada perkhidmatan AI (seperti Openaigpt) untuk mendapatkan jawapan pintar; 4. PHP kemudian memanggil TTSAPI (seperti sintesis Baidu atau Google Voice) untuk menukar balasan ke fail suara; 5. PHP mengalir fail suara kembali ke bahagian depan untuk bermain, menyelesaikan interaksi. Seluruh proses dikuasai oleh PHP untuk memastikan hubungan lancar antara semua pautan.

Cara Menggunakan PHP untuk Membina Fungsi Perkongsian Sosial PHP Perkongsian Interface Integration Practice Cara Menggunakan PHP untuk Membina Fungsi Perkongsian Sosial PHP Perkongsian Interface Integration Practice Jul 25, 2025 pm 08:51 PM

Kaedah teras untuk membina fungsi perkongsian sosial dalam PHP adalah untuk menghasilkan pautan perkongsian secara dinamik yang memenuhi keperluan setiap platform. 1. Mula -mula dapatkan halaman semasa atau URL dan maklumat artikel yang ditentukan; 2. Gunakan urlencode untuk menyandikan parameter; 3. Sambutan dan menjana pautan perkongsian mengikut protokol setiap platform; 4. Pautan paparan di hujung depan untuk pengguna mengklik dan berkongsi; 5. Dinamik menghasilkan tag OG pada halaman untuk mengoptimumkan paparan kandungan perkongsian; 6. Pastikan untuk melepaskan input pengguna untuk mencegah serangan XSS. Kaedah ini tidak memerlukan pengesahan yang kompleks, mempunyai kos penyelenggaraan yang rendah, dan sesuai untuk kebanyakan keperluan perkongsian kandungan.

Cara Menggunakan PHP Digabungkan dengan AI Untuk Mencapai Ralat Pembetulan Ralat PHP Pengesanan dan Pengoptimuman Sintaks PHP Cara Menggunakan PHP Digabungkan dengan AI Untuk Mencapai Ralat Pembetulan Ralat PHP Pengesanan dan Pengoptimuman Sintaks PHP Jul 25, 2025 pm 08:57 PM

Untuk merealisasikan pembetulan ralat teks dan pengoptimuman sintaks dengan AI, anda perlu mengikuti langkah -langkah berikut: 1. Pilih model AI atau API yang sesuai, seperti Baidu, Tencent API atau perpustakaan NLP sumber terbuka; 2. Panggil API melalui curl atau Guzzle PHP dan memproses hasil pulangan; 3. Maklumat pembetulan ralat paparan dalam aplikasi dan membenarkan pengguna memilih sama ada untuk mengadopsinya; 4. Gunakan php-l dan php_codesniffer untuk pengesanan sintaks dan pengoptimuman kod; 5. Secara berterusan mengumpul maklum balas dan mengemas kini model atau peraturan untuk meningkatkan kesannya. Apabila memilih AIAPI, fokus pada menilai ketepatan, kelajuan tindak balas, harga dan sokongan untuk PHP. Pengoptimuman kod harus mengikuti spesifikasi PSR, gunakan cache yang munasabah, elakkan pertanyaan bulat, mengkaji semula kod secara berkala, dan gunakan x

PHP Membuat Sistem Komen Blog untuk Mengewangkan Kajian Komen PHP dan Strategi Anti-Brush PHP Membuat Sistem Komen Blog untuk Mengewangkan Kajian Komen PHP dan Strategi Anti-Brush Jul 25, 2025 pm 08:27 PM

1. Memaksimumkan nilai komersil sistem komen memerlukan menggabungkan pengiklanan pengiklanan asli, perkhidmatan nilai tambah pengguna (seperti memuat naik gambar, komen top-up), mempengaruhi mekanisme insentif berdasarkan kualiti komen, dan pematuhan data pengewangan data tanpa nama; 2. Strategi audit harus mengadopsi gabungan penapisan kata kunci dinamik pra-audit dan mekanisme pelaporan pengguna, ditambah dengan penarafan kualiti komen untuk mencapai pendedahan hierarki kandungan; 3. Anti-brushing memerlukan pembinaan pertahanan berbilang lapisan: Recaptchav3 Pengesahan tanpa sensor, Honeypot Honeypot Field Robot, IP dan Had Frekuensi Timestamp menghalang penyiraman, dan pengiktirafan corak kandungan menandakan komen yang mencurigakan, dan terus berurusan dengan serangan.

Cara menggunakan PHP untuk menggabungkan AI untuk menjana imej. PHP secara automatik menjana karya seni Cara menggunakan PHP untuk menggabungkan AI untuk menjana imej. PHP secara automatik menjana karya seni Jul 25, 2025 pm 07:21 PM

PHP tidak secara langsung melaksanakan pemprosesan imej AI, tetapi mengintegrasikan melalui API, kerana ia adalah baik pada pembangunan web dan bukannya tugas-tugas intensif pengkomputeran. Integrasi API boleh mencapai pembahagian profesional buruh, mengurangkan kos, dan meningkatkan kecekapan; 2. Mengintegrasikan teknologi utama termasuk menggunakan Guzzle atau Curl untuk menghantar permintaan HTTP, pengekodan data JSON dan penyahkodan, pengesahan keselamatan utama API, pemprosesan giliran yang memakan masa yang memakan masa, pengendalian ralat yang teguh dan mekanisme semula, penyimpanan imej dan paparan; 3. Cabaran umum termasuk kos API daripada kawalan, hasil generasi yang tidak terkawal, pengalaman pengguna yang lemah, risiko keselamatan dan pengurusan data yang sukar. Strategi tindak balas menetapkan kuota dan cache pengguna, menyediakan panduan propt dan pemilihan multi-gambar, pemberitahuan asynchronous dan kemajuan kemajuan, penyimpanan pembolehubah persekitaran utama dan audit kandungan, dan penyimpanan awan.

PHP menyedari pengurusan inventori komoditi dan pengewangan PHP penyegerakan inventori dan mekanisme penggera PHP menyedari pengurusan inventori komoditi dan pengewangan PHP penyegerakan inventori dan mekanisme penggera Jul 25, 2025 pm 08:30 PM

PHP memastikan pemotongan inventori atomik melalui urus niaga pangkalan data dan kunci baris forupdate untuk mengelakkan overselling serentak yang tinggi; 2. Konsistensi inventori pelbagai platform bergantung kepada pengurusan berpusat dan penyegerakan yang didorong oleh peristiwa, menggabungkan pemberitahuan API/webhook dan beratur mesej untuk memastikan penghantaran data yang boleh dipercayai; 3. Mekanisme penggera harus menetapkan inventori rendah, sifar/inventori negatif, jualan yang tidak dapat dilepaskan, kitaran penambahan dan strategi turun naik yang tidak normal dalam senario yang berbeza, dan pilih DingTalk, SMS atau orang yang bertanggungjawab e -mel mengikut urgensi, dan maklumat penggera mesti lengkap dan jelas untuk mencapai penyesuaian perniagaan dan tindak balas yang cepat.

Cara Menggunakan PHP untuk membangunkan Platform Komuniti Q & A Penjelasan terperinci mengenai model pengewangan komuniti interaktif PHP Cara Menggunakan PHP untuk membangunkan Platform Komuniti Q & A Penjelasan terperinci mengenai model pengewangan komuniti interaktif PHP Jul 23, 2025 pm 07:21 PM

1. 2. Prestasi tinggi memerlukan pergantungan pada cache (redis), pengoptimuman pangkalan data, CDN dan giliran tak segerak; 3. Keselamatan mesti dilakukan dengan penapisan input, perlindungan CSRF, HTTPS, penyulitan kata laluan dan kawalan kebenaran; 4. Pengiklanan pilihan wang, langganan ahli, ganjaran, komisen, pembayaran pengetahuan dan model lain, terasnya adalah untuk memadankan nada komuniti dan keperluan pengguna.

Beyond the Lamp Stack: Peranan PHP dalam Senibina Enterprise Moden Beyond the Lamp Stack: Peranan PHP dalam Senibina Enterprise Moden Jul 27, 2025 am 04:31 AM

Phpisstillrelevantinmodernenterpriseenvironments.1.modernphp (7.xand8.x) Menawarkan Perpaduan Perlengkapan, ketegangan, jitcompilation, danmodernsyntax, makeitsuatableforlarge-scaleapplications.2.phpintegratefective

See all articles