Bilangan Maksimum Mata dengan Kos

1937. Bilangan Mata Maksimum dengan Kos

Kesukaran: Sederhana

Topik: Tatasusunan, Pengaturcaraan Dinamik

Anda diberi mata matriks integer m x n (0-diindeks). Bermula dengan 0 mata, anda mahu memaksimumkan bilangan mata yang anda boleh dapat daripada matriks.

Untuk mendapatkan mata, anda mesti memilih satu sel dalam setiap baris. Memilih sel pada koordinat (r, c) akan menambahkan mata[r][c] pada skor anda.

Walau bagaimanapun, anda akan kehilangan mata jika anda memilih sel terlalu jauh daripada sel yang anda pilih dalam baris sebelumnya. Untuk setiap dua baris bersebelahan r dan r + 1 (di mana 0 <= r < m - 1), memilih sel pada koordinat (r, c₁) dan (r + 1, c ₂) akan menolak abs(c₁ - c₂) daripada markah anda.

Kembali bilangan maksimum mata yang boleh anda capai.

abs(x) ditakrifkan sebagai:

• x untuk x >= 0.

• -x untuk x < 0.

Contoh 1:

• Input: l1 = [2,4,3], l2 = [5,6,4]
• Output: 9
• Penjelasan:
  • Sel biru menandakan sel optimum untuk dipilih, yang mempunyai koordinat (0, 2), (1, 1) dan (2, 0).
  • Anda menambah 3 + 5 + 3 = 11 pada markah anda.
  • Walau bagaimanapun, anda mesti menolak abs(2 - 1) + abs(1 - 0) = 2 daripada markah anda.
  • Skor akhir anda ialah 11 - 2 = 9.

Contoh 2:

• Input: mata = [[1,5],[2,3],[4,2]]
• Output: 11
• Penjelasan:
  • Sel biru menandakan sel optimum untuk dipilih, yang mempunyai koordinat (0, 1), (1, 1) dan (2, 0).
  • Anda menambah 5 + 3 + 4 = 12 pada markah anda.
  • Walau bagaimanapun, anda mesti menolak abs(1 - 1) + abs(1 - 0) = 1 daripada markah anda.
  • Skor akhir anda ialah 12 - 1 = 11.

Kekangan:

• m == mata.panjang
• n == mata[r].panjang
• 1 <= m, n <= 10⁵
• 1 <= m * n <= 10⁵
• 0 <= mata[r][c] <= 10⁵

Petunjuk:

1. Cuba gunakan pengaturcaraan dinamik.
2. dp[i][j] ialah bilangan maksimum mata yang boleh anda miliki jika mata[i][j] ialah sel terbaharu yang anda pilih.

Penyelesaian:

Kami boleh memecahkan penyelesaian kepada beberapa langkah:

Langkah 1: Tentukan Tatasusunan DP

Kami akan menggunakan dp tatasusunan 2D di mana dp[i][j] mewakili mata maksimum yang boleh kami capai dengan memilih sel pada baris i dan lajur j.

Langkah 2: Mulakan Tatasusunan DP

Mulakan baris pertama dp supaya sama dengan baris pertama mata kerana tiada baris sebelumnya untuk menolak kos.

Langkah 3: Kira Nilai DP untuk Setiap Baris

Untuk setiap baris berikutnya, kami mengira mata maksimum yang mungkin untuk setiap lajur dengan mengambil kira kos penukaran daripada baris sebelumnya.

Untuk mengira peralihan dari baris i-1 ke baris i dengan cekap, kita boleh menggunakan dua tatasusunan tambahan kiri dan kanan:

• left[j] akan menyimpan nilai maksimum yang boleh kita capai untuk lajur ke-j dengan mengambil kira peralihan dari kiri sahaja.
• right[j] akan menyimpan nilai maksimum yang boleh kita capai untuk lajur ke-j dengan mengambil kira peralihan dari kanan sahaja.

Langkah 4: Kemas kini DP untuk Setiap Baris

Untuk setiap lajur j dalam baris i:

• Kemas kini dp[i][j] menggunakan maksimum sama ada kiri[j] atau kanan[j] tambah mata[i][j].

Langkah 5: Kembalikan Nilai Maksimum dari Baris Terakhir

Hasilnya ialah nilai maksimum dalam baris terakhir tatasusunan dp.

Mari laksanakan penyelesaian ini dalam PHP: 1937. Bilangan Mata Maksimum dengan Kos

  
  
  Penjelasan:




tatasusunan kiri dan kanan: Ini membantu kami mengira mata maksimum yang boleh kami peroleh untuk setiap sel dengan mempertimbangkan nilai baris sebelumnya, dengan cekap mengambil kira penalti daripada bergerak merentas lajur.

Pendekatan pengaturcaraan dinamik: Kaedah ini memastikan setiap baris dikira berdasarkan baris sebelumnya, menjadikan penyelesaian berskala untuk matriks besar.


Pendekatan ini mempunyai kerumitan masa sebanyak (O(m kali n)), yang cekap memandangkan kekangan.

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 Bilangan Maksimum Mata dengan Kos. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!