Informatyka. Konkursy i algorytmy
Algorytm dynamiczny
Do czego służy?
Algorytm dynamiczny służy do rozwiązywania problemów, dla których zachodzi taki warunek:
Dany problem można obliczyć korzystając z wyników z mniejszych podproblemów tego
problemu.
Licząc rozwiązanie danego nam problemu liczymy najpierw rozwiązania
wszystkich mniejszych podproblemów i na koniec korzystając z wcześniejszych wyników
liczymy końcowy wynik dla całego problemu. Poniżej opiszę jeden z wielu algorytmów
dynamiczny. (jeden z najprostszych)
Algorytm
Mamy daną podłużną planszę o długości n. Niektóre pola są na niej zablokowane, mamy
jednak gwarancję, że pole nr 1 ani pole nr n nie są zablokowane. Mamy powiedzieć na ile
sposobów możemy dojść z pola 1 na pole n nie wchodząc na żadne zablokowane pole, jeśli
możemy naraz przejść 1 pole lub 2 pola.
Na początku ustawiamy wartość w polu nr 1 na 1 (możemy tam dojść na dokładnie 1 sposób -
od razu tam jesteśmy). Potem jeżeli pole nr 2 nie jest zablokowane to ustawiamy je na 2
(możemy 2 razy skoczyć o 1 lub raz skoczyć o 2). Następnie dla każdego niezablokowanego
pola wynikiem będzie dyn[i-1]+dyn[i-2], gdzie dyn to tablica gdzie przechowujemy
wyniki dla każdego kolejnego pola, a i to numer pola, które aktualnie rozpatrujemy.
Przykład
Pole zablokowane jest oznaczone jako Z, a pole wolne jest oznaczone jako W. Zasymulujmy
nasz algorytm dla przykładowej planszy:
WWWWZW
1 2 3 4 5 6 (indeksy w tablicy z wynikami)
0 0 0 0 0 0 (wartości w tablic z wynikami)
1 0 0 0 0 0
1 2 0 0 0 0
1 2 3 0 0 0
1 2 3 5 0 0
1 2 3 5 0 0 (natrafiliśmy na zablokowane pole)
1 2 3 5 0 5
Tutaj kończymy nasz algorytm (doszliśmy do ostatniego pola). Wynikiem dla tego przykładu
będzie 5.
Implementacja i złożoność
implementacja w c++:int plansza[MAXI];
int dyn[MAXI];
const int mod = 1e9 + 7;
int dynamik(int n){
dyn[1] = 1;
if(plansza[2] == 0){
dyn[2] = 2;
}
for(int i = 3; i <=n ; i++){
if(plansza[i] == 1){
continue;
}
dyn[i] = dyn[i - 1] + dyn[i - 2];
dyn[i] %= mod;
}
return dyn[n];
}
implementacja w python:
plansza = [0 for i in range(1000007)]
def dynamik(n):
dyn[1] = 1
if(plansza[2] == 0):
dyn[2] = 2
for i in range(3, n + 1):
if(plansza[i] != 1):
dyn[i] = dyn[i - 1] + dyn[i - 2]
dyn[i] = dyn[i] % 1000000007
return dyn[n]
złożoność: