Project Eulerをrubyで解くの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
