Ne pasă de confidențialitatea datelor dvs. HackerEarth folosește informațiile pe care le furnizați pentru a vă oferi conținut, produse și servicii actualizate.

care

Politica noastră de confidențialitate și Termenii și condițiile vă vor ajuta să înțelegeți cum vă controlați datele pe HackerEarth.

Înscrieți-vă și obțineți acces gratuit la peste 100 de tutoriale și probleme de practică Începeți

1. Introducere

Există multe probleme în concursurile de codare online care implică găsirea unei căi de cost minim într-o grilă, găsirea numărului de modalități de a ajunge la o anumită poziție dintr-un punct de plecare dat într-o grilă 2-D și așa mai departe. Această postare încearcă să analizeze abordarea de programare dinamică pentru a rezolva aceste probleme. Problemele care vor fi discutate aici sunt:

2. Găsirea căii cu costuri minime într-o matrice 2-D

Declarație problemă: Având în vedere o matrice de cost Cost [] [] unde Cost [i] [j] reprezintă Costul vizitei celulei cu coordonatele (i, j), găsiți o cale min-cost pentru a ajunge la o celulă (x, y) din celula 0,0 ) cu condiția să puteți călători doar cu un pas la dreapta sau cu un pas în jos. (Presupunem că toate costurile sunt numere întregi pozitive)

Soluţie: Este foarte ușor să rețineți că, dacă ajungeți la o poziție (i, j) în grilă, trebuie să fi venit de la o celulă mai mare, adică (i-1, j) sau dintr-o celulă la stânga, adică (i, j-1). Aceasta înseamnă că costul vizitei celulei (i, j) va proveni din următoarea relație de recurență:

Afirmația de mai sus înseamnă că pentru a atinge celula (i, j) cu costul minim, ajungeți mai întâi la celula (i-1, j) sau la celula (i, j-1) la un cost cât mai mic posibil. De acolo, săriți la celulă (i, j). Acest lucru ne aduce la cele două condiții importante care trebuie îndeplinite pentru o problemă de programare dinamică:

Sub-structură optimă: - Soluția optimă la o problemă implică soluții optime la subprobleme.

Sub-probleme suprapuse: - Subproblemele odată calculate pot fi stocate într-un tabel pentru utilizare ulterioară. Acest lucru economisește timpul necesar pentru a calcula aceleași subprobleme din nou și din nou.

(Puteți să căutați în google cei doi termeni de mai sus pentru mai multe detalii)

Problema găsirii căii min-cost este acum aproape rezolvată. Acum calculăm valorile cazurilor de bază: rândul de sus și coloana din stânga. Pentru rândul de sus, o celulă poate fi accesată numai din celula din stânga acesteia. Presupunând index bazat pe zero,

adică cost pentru atingerea celulei (0, j) = Cost pentru atingerea celulei (0, j-1) + Cost pentru vizitarea celulei (0, j) În mod similar,

adică cost pentru atingerea celulei (i, 0) = Cost pentru atingerea celulei (i-1,0) + Cost pentru vizitarea celulei (i, 0)

Alte valori pot fi calculate din acestea. Consultați codul de mai jos pentru mai multe înțelegeri.

O altă variantă a acestei probleme include o altă direcție de mișcare, adică se permite, de asemenea, să se deplaseze diagonal mai jos de la celula (i, j) la celula (i + 1, j + 1). Această întrebare poate fi, de asemenea, rezolvată cu ușurință utilizând o ușoară modificare a relației de recurență. Pentru a ajunge la (i, j), trebuie să ajungem mai întâi la (i-1, j), (i, j-1) sau (i-1, j-1).

2. Găsirea numărului de modalități de a ajunge de la o poziție inițială la o poziție finală călătorind numai în direcții specificate.

Declarație problemă: Având în vedere o matrice 2-D cu M rânduri și N coloane, găsiți numărul de modalități de a ajunge la celulă cu coordonatele (i, j) de la celula de pornire (0,0) cu condiția să puteți parcurge doar un pas la dreapta sau unul demisionează.

Soluţie: Această problemă este foarte asemănătoare cu cea anterioară. Pentru a ajunge la o celulă (i, j), trebuie mai întâi să ajungeți fie la celulă (i-1, j), fie la celulă (i, j-1) și apoi să vă deplasați cu un pas în jos sau, respectiv, la dreapta pentru a ajunge la celulă ( i, j). După ce ne-am convins că această problemă într-adevăr satisface structura optimă și proprietățile subproblemelor suprapuse, încercăm să formulăm o soluție de programare dinamică de jos în sus.

Mai întâi trebuie să identificăm statele de care va depinde soluția. Pentru a găsi numărul de modalități de a ajunge la o poziție, care sunt variabilele de care depinde răspunsul meu? Aici, avem nevoie de numărul rândului și al coloanei pentru a identifica în mod unic o poziție. Pentru mai multe detalii despre modul de a decide starea unei soluții de programare dinamică, consultați acest lucru: Cum se poate începe rezolvarea problemelor de programare dinamică? Prin urmare, să fie NumWays (i, j) numărul de modalități de a ajunge la poziția (i, j). După cum sa menționat mai sus, numărul de modalități de a ajunge la celula (i, j) va fi egal cu suma numărului de modalități de a ajunge (i-1, j) și a numărului de modalități de a ajunge (i, j-1) . Astfel, avem relația noastră de recurență ca:

Acum, tot ce trebuie să faceți este să aveți grijă de cazurile de bază, iar relația de recurență va calcula restul pentru dvs.:)

Cazul de bază, ca la întrebarea anterioară, este rândul de sus și coloana din stânga. Aici, fiecare celulă din rândul de sus poate fi vizitată într-un singur mod, adică din celula stângă. Similar este cazul pentru coloana din stânga. Prin urmare, codul este:

3. Găsirea numărului de modalități de a ajunge la o anumită poziție într-o grilă dintr-o poziție de pornire (având în vedere unele celule blocate)

Declarație problemă: Puteți citi afirmația problemei aici: Roboți și căi de intrare sunt trei numere întregi M, N și P care indică numărul de rânduri, numărul de coloane și numărul de celule blocate, respectiv. În următoarele linii P, fiecare linie are exact 2 numere întregi i și j denotând că celula (i, j) este blocată.

Soluţie: Codul de mai jos explică cum să procedați cu soluția. Problema este aceeași cu cea precedentă, cu excepția câtorva verificări suplimentare (din cauza celulelor blocate).

O altă variantă

În cele din urmă, discutăm o altă variantă a problemelor care implică rețelele. Puteți vedea problema aici. O scurtă descriere a problemei este:

Declarație problemă: Vi se oferă o matrice 2-D A de n rânduri și m coloane în care A [i] [j] denotă caloriile arse. Două persoane, un băiat și o fată, pornesc din cele două colțuri ale acestei matrice. Băiatul începe de la celulă (1,1) și trebuie să ajungă la celulă (n, m). Pe de altă parte, fata începe de la celulă (n, 1) și trebuie să ajungă (1, m). Băiatul se poate mișca în dreapta și în jos. Fata se poate mișca în dreapta și în sus. Pe măsură ce vizitează o celulă, cantitatea din celula A [i] [j] se adaugă la numărul total de calorii arse. Trebuie să maximizați suma totală a caloriilor arse de ambele, cu condiția ca acestea să se întâlnească doar într-o singură celulă și costul acestei celule să nu fie inclus în niciuna din totalul lor.

Soluţie: Să analizăm această problemă în pași:

Băiatul poate întâlni fata într-o singură celulă.

Deci, să presupunem că se întâlnesc la celulă (i, j).

Băiatul poate intra de la stânga sau de sus, adică (i, j-1) sau (i-1, j). Acum se poate deplasa la dreapta sau în jos. Adică, secvența pentru băiat poate fi:

În mod similar, fata poate intra din stânga sau jos, adică (i, j-1) sau (i + 1, j) și ea poate merge în sus sau la dreapta. Secvența pentru mișcarea fetei poate fi:

Comparând cele 4 secvențe ale băiatului și ale fetei, băiatul și fata se întâlnesc doar într-o poziție (i, j), dacă nu

Convinge-te că în niciun alt caz nu se vor întâlni într-o singură poziție.

Acum, putem rezolva problema creând 4 tabele:

  1. Călătoria băiatului de la început (1,1) până la celula de întâlnire (i, j)
  2. Călătoria băiatului de la celula de întâlnire (i, j) până la sfârșit (n, m)
  3. Călătoria fetei de la început (n, 1) până la celula de întâlnire (i, j)
  4. Călătoria fetei de la celula de întâlnire (i, j) până la sfârșit (1, n)

Celula de întâlnire poate varia de la 2

Consultați codul de mai jos pentru mai multe detalii:

Mulțumesc pentru lectură.:) Sper că a fost de ajutor!