###### tags: `Zajęcia SP76`

# Stokrotki

Stokrotki to kolejny ciekawy przykład programowania dynamicznego, który pokazuje nam jak w wielu zastosowaniach pracowanie na tak drobnych podproblemach jak tutaj pomoże nam szybko znaleźć optymalne rozwiązanie w zadaniu gdzie istnieje tak wiele potencjalnych rozwiązań.

W zadaniu dostajemy prostokątną planszę. Na każdym polu znajduje się nieujemna liczba stokrotek. Musimy przejść przez planszę od lewej do prawej krawędzi w taki sposób, by zdeptać jak najmniej tych wspaniałch kwiatów.

Trasa może zacząć się na dowolnym polu w skrajnie lewej kolumnie i skończyć na dowolnym polu w skrajnie prawej kolumnie. W każdym ruchu możemy poruszać się jedynie w prawo, ale możemy poruszać się też po skosach.

## Wypełnianie tablicy podproblemów

Jak zwykle kluczem do znalezienia optymalnego rozwiązania jest znalezienie takiego podziału problemu na podproblemy, by każdy podbroblem można było szybko otrzymać z kilku inny podproblemów. Zauważmy, że gdybyśmy chcieli przeanalizować każdą trasę do dla $m$ początkowych pól musilibyśmy zbadać 3 rozgałęzienia, a dla każdego z tych 3 rozwiązań kolejne 3 rozgałęzienia itd.

W tym zadaniu (podobnie jak w zadaniu róże - jak kilkoro z was zauważyło) wystarczy, że patrzymy tylko na poprzednią kolumnę! Naszym podbroblem będzie jak optymalnie dojść do pola $(x, y)$.

Zobaczmy: skoro dla każdego pola możemy przejść z kolumny $n-1$ do kolumny $n$ tylko z pola w tym samym wierszu lub ewentualnie z wierszy przylegających to wystarczy sprawdzić tylko te 3 pola, wybrać optymalny z nich i dodać wartość stokrotek na danym polu. Dlaczego to działa? Musimy założyć, że te pola z których korzystamy są już poprawnie wypełnione, ale skoro idziemy od lewej do prawej, to oczywiście będą one poprawnie wypełnione.


inicjalizacja danych

dla każdej kolumny x:
	dla każdego wiersza y:
		optymalna wartość pól poprzednich := min(pole(x - 1, y - 1),
												pole(x - 1, y),
												pole(x - 1, y + 1))
		pole(x, y) := pole(x, y) + optymalna wartość pól poprzednich 

Na koniec wystarczy sprawdzić w którym polu w ostatniej kolumnie otrzymaliśmy minimalną wartość

## Odtwarzanie drogi
Ok, to znamy optymalną wartość, ale jak znaleźć drogę, którą powinniśmy przejść? Okazuje się, że z wypełnioną tablicą podproblemów to nic trudnego!

W którym polu kończymy? Robiliśmy to w poprzednim zadaniu. Trzeba znaleźć minimalną wartość ostatniej kolumny. Ok, czyli w tym polu kończymy.

Teraz tak naprawdę znamy już całą drogę powrotną, ponieważ wiemy skąd przyszliśmy! Z 3 dostępnych pól musimy zawsze wybierać pole minimalne, aż do lewej kolumny.

## Zmiana zasad
W zadaniu stokrotki 3 dochodzą nowe zasady. Mamy kolejne możliwośći podróżowania. To zadanie nie byłoby trudne gdyby nie to, że musimy zmienić sposób przechodzenia po tablicy. Zauważmy, że gdy przechodzimy po tablicy tak jak wcześniej to jedno z pól nie jest jeszcze poprawnie wypełnione, czyli cały algorytm nie da poprawnego wyniku.


Istnieje kilka sposobów objeścia tego problemu. Ja zalecam rozbić to zadanie na następujące podzadania:
- Można poruszać się tak samo jak w zadaniach 1 i 2 oraz dodatkowo z góry
- Można poruszać się tak samo jak w zadaniach 1 i 2 oraz dodatkowo z dołu
- Obliczyć obie wersje zadania dla danej kolumny i sprawdzić czy nie można coś z tego wywnioskować.

Zobaczmy jak to będzie wyglądało na obrazku: