Bilangan Maksimum Pergerakan dalam Grid

Linda Hamilton
Lepaskan: 2024-10-30 13:27:03
asal
276 orang telah melayarinya

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:

Maximum Number of Moves in a Grid

  • 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:

Maximum Number of Moves in a Grid

  • 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 <= 105
  • 1 <= grid[i][j] <= 106

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:

  1. Permulaan dp: Kami mencipta dp tatasusunan 2D untuk menyimpan pergerakan maksimum daripada setiap sel.
  2. 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.
  3. 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!

sumber:dev.to
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
Artikel terbaru oleh pengarang
Tutorial Popular
Lagi>
Muat turun terkini
Lagi>
kesan web
Kod sumber laman web
Bahan laman web
Templat hujung hadapan
Tentang kita Penafian Sitemap
Laman web PHP Cina:Latihan PHP dalam talian kebajikan awam,Bantu pelajar PHP berkembang dengan cepat!