Programare dinamică - Probleme care implică Grids HackerEarth
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.
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).