Route e spazio campione

[Xorik]

Ciao a tutti,
vi pongo subito il problema nato all'uni.
Data una griglia così composta:

A B C D
E F G H
I L M N
O P Q R

e potendomi muovere solo in orizzontale /verticale Quanti percorsi esistono da A a M?
Non valgono cicli e 1 percorso può essere usato solo 1 volta.
Sinceramente non so proprio da dove cominciare; pensavo di contare tutti i possibili percorsi da i a j ma anche e poi per esclusione togliere quelli che non mi servono, però non so come fare. C'è un metodo più rapido?
Grazie

[onlyReferee]

Ciao Xorik
Ti posso dare delle dritte a livello teorico da cui puoi poi provare a partire. Per risolvere questo problema c'è bisogno di definire una sottostruttura ottima utile per arrivare alla nostra soluzione. Questa caratteristica è comune sia nell'approccio della programmazione dinamica che in quello goloso (greedy in inglese). L'approccio greedy non credo possa rivelarsi utile in questo caso però in quanto dovendo enumerare tutti i percorsi che vanno da un punto all'altro ($A$ ed $M$ in questo caso) non siamo interessati ad avere una soluzione ottima. La strada da seguire è dunque la programmazione dinamica a mio giudizio.
Spero di esserti stato d'aiuto, anche semplicemente a livello intuitivo.