Bilangan Maksimum Pergerakan dalam Grid

2684. Bilangan Maksimum Pergerakan dalam Grid

Kesukaran: Sederhana

Topik: Tatasusunan, Pengaturcaraan Dinamik, Matriks

Anda diberi 0-diindeks grid matriks m x n yang terdiri daripada positif integer.

Anda boleh bermula di mana-mana sel dalam lajur pertama matriks dan melintasi grid dengan cara berikut:

• Daripada sel (baris, kol), anda boleh beralih ke mana-mana sel: (baris - 1, kol 1), (baris, kol 1) dan (baris 1, kol 1) supaya nilai sel yang anda pindahkan, hendaklah secara ketat lebih besar daripada nilai sel semasa.

Kembalikan bilangan maksimum gerakan yang boleh anda lakukan.

Contoh 1:

• Input: grid = [[2,4,3,5],[5,4,9,3],[3,4,2,11],[10,9,13,15] ]
• Output: 3
• Penjelasan: Kita boleh mulakan di sel (0, 0) dan membuat langkah berikut:
  • (0, 0) -> (0, 1).
  • (0, 1) -> (1, 2).
  • (1, 2) -> (2, 3). Ia boleh ditunjukkan bahawa ia adalah bilangan maksimum pergerakan yang boleh dibuat.

Contoh 2:

• Input: grid = [[3,2,4],[2,1,9],[1,1,7]]
• Output: 0
• Penjelasan: Bermula dari mana-mana sel dalam lajur pertama, kami tidak boleh melakukan sebarang pergerakan.

Kekangan:

• m == grid.panjang
• n == grid[i].panjang
• 2 <= m, n <= 1000
• 4 <= m * n <= 10⁵
• 1 <= grid[i][j] <= 10⁶

Petunjuk:

1. Pertimbangkan menggunakan pengaturcaraan dinamik untuk mencari bilangan maksimum pergerakan yang boleh dibuat daripada setiap sel.
2. Jawapan akhir ialah nilai maksimum dalam sel lajur pertama.

Penyelesaian:

Kita boleh menggunakan Pengaturcaraan Dinamik (DP) untuk menjejaki bilangan maksimum pergerakan daripada setiap sel, bermula dari mana-mana sel dalam lajur pertama. Berikut ialah pendekatan langkah demi langkah:

Pendekatan:

1. Tentukan Tatasusunan DP: Biarkan dp[row][col] mewakili bilangan maksimum pergerakan yang mungkin bermula dari grid[row][col]. Mulakan ini dengan 0 untuk semua sel.

2. Melintasi Grid:

   • Mulakan dari lajur terakhir dan bergerak ke belakang ke lajur pertama. Untuk setiap sel dalam kol lajur, kira kemungkinan pergerakan untuk kol-1.
   • Kemas kini dp[row][col] berdasarkan kemungkinan pergerakan (baris - 1, kol 1), (baris, kol 1) dan (baris 1, kol 1), hanya jika nilai sel destinasi ialah lebih hebat daripada sel semasa.

3. Kira Pergerakan Maksimum:

   • Selepas mengisi jadual dp, hasilnya akan menjadi nilai maksimum dalam lajur pertama dp, kerana ia mewakili pergerakan maksimum bermula dari mana-mana sel dalam lajur pertama.

4. Kes Tepi:

   • Kendalikan kes di mana tiada pergerakan boleh dilakukan (mis., apabila semua laluan disekat oleh nilai yang lebih rendah atau sama dalam sel jiran).

Mari laksanakan penyelesaian ini dalam PHP: 2684. Bilangan Maksimum Pergerakan dalam Grid

  
  
  Penjelasan:




Permulaan dp: Kami mencipta dp tatasusunan 2D untuk menyimpan pergerakan maksimum daripada setiap sel.

Gelung melalui Lajur: Kami mengulangi daripada lajur kedua terakhir kepada lajur pertama, mengemas kini dp[row][col] berdasarkan kemungkinan pemindahan ke sel jiran dalam lajur seterusnya.

Pengiraan Pergerakan Maksimum: Akhir sekali, nilai maksimum dalam lajur pertama dp memberikan hasil.



  
  
  Analisis Kerumitan:




Kerumitan Masa: O(m x n) kerana kami memproses setiap sel sekali.

Kerumitan Angkasa: O(m x n) untuk tatasusunan dp.


Penyelesaian ini cekap memandangkan kekangan dan akan berfungsi dalam had yang disediakan.

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 Pergerakan dalam Grid. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!