なんじゃくにっき2

ほげほげ。プログラミングの話題中心。ほか資格とか。

Project Euler 81 Path sum: two ways

Project Eulerrubyで解くの81番目。 順番に解くのに飽きてきたので適当にやっていきます。

Problem 81Problem 81 - Project Euler

Path sum: two ways

Find the minimal path sum, in matrix.txt (right click and "Save Link/Target As..."), a 31K text file containing a 80 by 80 matrix, from the top left to the bottom right by only moving right and down.

costが最小になる経路を求めよって問題で、単純に全組み合わせを計算するのは時間がかかりすぎる。 途中経路の値を記憶させておけばOK。 座標(x, y)までのコストは座標(x -1, y)までか座標(x, y -1)までかのコストの小さい方プラスx, y地点のコスト。

x, yを小さい方から積み上げて計算しても良いんですが、せっかくなので再帰で書いてみました。 github.com