Zadania na tablicach dwuwymiarowych

Często w trudniejszych zadaniach można się spotkać z takim problemem że trza wyszukać najkrótszą drogę albo najmniejszą wartość drogi przyjmując że pole każde ma cyfrę a wartość jest sumą z jednego miejsca do drugiego.

Przykładowe zadania:
http://main.edu.pl/pl/archive/ilocamp/2010/las
http://www.ii.pwr.wroc.pl/uploads/images/do_zawody/zadania2011/uczniowie/DZwPZ_11_Uczniowie_B_Robot.pdf
http://www.ii.pwr.wroc.pl/uploads/images/do_zawody/zadania2011/uczniowie/DZwPZ_11_Uczniowie_E_Labirynt.pdf

I drapie mnie ten problem od miesięcy ponieważ nie mogę wpaść jak takie zadania robić.
Z początku zastanawiałem się aby użyć rekurencji, ale nie wpadłem jak ją wykorzystać. ;/

Proszę o podpowiedzi co w takich zadaniach powinno się użyć i w jaki sposób.

Pozdrawiam

Z początku zastanawiałem się aby użyć rekurencji, ale nie wpadłem jak ją wykorzystać. ;/

Zgadza sie mozna, tu wykorzystac rekurencje z cacheowaniem wynikow, zeby przyspieszyc algorytm.
Wzor rekurencyjny dla zadanie z 2 linki moze wygladac tak:
c(x,y) = c(x-1,y) + c(x,y-1)
c(0,0) = 1
Gdzie c(x, y) oznacza liczbe drog z punktu startowego do punktu (x, y). Czyli liczba drog do punktu (x, y) jest suma liczby drog do punktu (x-1, y) i do punktu (x, y-1).
Oczywiscie musisz rozpatrzyc rozne przypadki jak wyjscie poza plansze, przeszkody a takze zapisywac wyniki, zeby nie liczyc ilosc drog po kilka razy dla tego samego punktu.

Zadanie z 3 linku mozna rozwiazac algorytmem Dijkstry.
Z kolei zadanie z pierwszego linku to zupelnie inne zadanie, chociaz pozornie podobne. Mozna go rozwiazac programowaniem dynamicznym.

Algorytm Dijkstry oraz jego późniejsze modyfikacje. W zasadzie działa na krawędziach grafu ale można założyć że masz graf w którym są krawędzie tylko do sąsiednich węzłów z wagą która jest wpisana w wierzchołku docelowym.

Dziękuję bardzo, już się domyślam jak zrobić te 2 zadanka. Ale Las nadal stanowi problem.
Mógłbyś lekko naprowadzić co miałeś na myśli pisząc programowanie dynamiczne?

Masz problem z dynamizmem w tym zadaniu czy ogólnie?
Jeżeli ogólnie to:
http://pl.wikipedia.org/wiki/Najdłuższy_wspólny_podciąg - algorytm rozwiązujący ten problem to dwuwymiarowy dynamik. Przeanalizuj go. ;)