>  > Seems like a comp sci homework problem to me, as it is a classic example
>  > of where you can use dynamic programming.  Seehttp://en.wikipedia.org/wiki/Dynamic_prog
ramming
> 
>  Actually It's not homework. You don't normally get homework at my age.
>  Just something I thought would be interesting..
> 
>  > I think it's a perfect quiz for Ruby Quiz.
> 
>  Ah ok, shows how wrong I was.. I'll submit something to Ruby Quiz.
>  Thanks.

Shouldn't this easily and optimally solvable with Dijkstra's
algorithm:
http://en.wikipedia.org/wiki/Dijkstra's_algorithm

Dijkstra solves the problem bottom-up, solving smaller problems first
and then solve the next bigger problem. One just has to make sure to
negate the optimizer condition and to walk north and west (because
Dijkstra's algorithm returns the previous nodes of the path, not the
next nodes). This should be in sense of "dynamic programming" as
mentioned before.

Regards,
Kai