問題

In the 5 by 5 matrix below, the minimal path sum from the top left to the bottom right, by only moving to the right and down, is indicated in bold red and is equal to 2427.
以下の5*5のマトリックスで、左上の隅から右下の隅に右移動→と下移動↓だけで移動した場合、経路上にある数字の合計の最小値は、赤く示されている数字の合計で2427になる。

\begin{pmatrix}
\color{red}{131} & 673 & 234 & 103 & 18\\
\color{red}{201} & \color{red}{96} & \color{red}{342} & 965 & 150\\
630 & 803 & \color{red}{746} & \color{red}{422} & 111\\
537 & 699 & 497 & \color{red}{121} & 956\\
805 & 732 & 524 & \color{red}{37} & \color{red}{331}
\end{pmatrix}

Find the minimal path sum from the top left to the bottom right by only moving right and down in matrix.txt (right click and "Save Link/Target As..."), a 31K text file containing an 80 by 80 matrix.
matrix.txtに書かれている80*80のマトリックスで左上の隅から右下の隅に右移動→と下移動↓だけで移動した場合の経路上にある数字の最小の合計値を求めよ。

全パターン試すのは無理

「右移動か下移動か」を160回繰り返すので、2の160乗分のパターンを計算しないといけません。ちなみに2の160乗をGoogleに聞いてみたら1.46150163733 * (10の48乗)って出ました。ヒェェ

動的計画法

調べるとみんな動的計画法（Dynamic Programming）という方法で解いているらしい、ということはわかったけど、他の人のコード見てもピンとこなくて3日くらい考えてやっとわかりました

この問題では左上から順番に各セルに到達するための最小の合計値を計算していきます。
3*3のマトリックスだとこんな感じ

一番左上の1のセルは足すモノがないので最小合計値は1（赤で書いた数字が最小合計値）
1段目真ん中のセルに到達するには右移動→しか無いので左のセルの最小合計値1を足して最小合計値は3
1段目右端のセルに到達する場合も右移動→しか無いので左のセルへの最小合計値3を足して最小合計値は6
2段目左端のセルに到達するには下移動↓しか無いので上のセルの最小合計値1を足して最小合計値は5
2段目真ん中のセルに到達するには右移動→と下移動↓があるので、二つの数字を比べて小さい方の数字3を足し、最小合計値は8
...（右下のセルまで繰り返し）

小さい範囲の最小合計値を求めて、それを広げていくという方法を取ることで、すでに計算した部分を再計算する必要がないため、単純なループで解くことができます。ちなみに80*80のマトリックスをGoで実行したところ1.4秒しかかかりませんでした。

Goで書いてみた

package main

import (
    "fmt"
    "os"
    "bufio"
    "strings"
    "strconv"
    "time"
)

func main() {
    // タイマーをスタート.
    start := time.Now()

    // テキストファイルからデータを取り込む.
    lines := getLines()

    // 動的計画法で最小経路を取得する.
    for i := 0; i < len(lines); i++ {
        for j := 0; j < len(lines[0]); j++ {
            var min int
　　　　　　　// 左上のセルでは何もしない.
            if i == 0 && j == 0 {
                continue;
            // 一番上の段では左のセルの値を取得.
            } else if i == 0 {
                min = lines[i][j-1]
            // 一番左の列では上のセルの値を取得.
            } else if j == 0 {
                min = lines[i-1][j]
            // 通常のセルでは左と上を比べて小さい方の値を取得.
            } else {
                top := lines[i-1][j]
                left := lines[i][j-1]
                min = getMin(top, left)
            }

            // 現在のセルの値をこのセルまでの最小合計値で書き換える.
            lines[i][j] += min;
        }
    }

    // 結果を出力.
    fmt.Println(lines[len(lines) - 1][len(lines[0]) - 1])

    // 実行時間を出力.
    elapsed := time.Since(start)
	fmt.Printf("The execution took %s", elapsed)
}

func getLines() [][]int {
    // ファイルを開く.
    file, err := os.Open("matrix.txt")
    if err != nil {
        fmt.Println("Error opening file!!!")
    }

    // 他の処理が終わったらファイルを閉じる.
    defer file.Close()

   // Get the scanner.
    scanner := bufio.NewScanner(file)

    // 全ての数字.
    var lines [][] int

    // 一行ずつ読み込む.
    for scanner.Scan() {
        // コンマ区切りの文字列("1,2,3,4....").
        text := scanner.Text()

        // スライスにする(["1","2","3","4"...]).
        lineString := strings.Split(text, ",")

        // 数字をintにする([1, 2, 3, 4...]).
        var lineInt [] int
        for index := 0; index < len(lineString); index++ {
            integer, _ := strconv.Atoi(lineString[index])
            lineInt = append(lineInt, integer)
        }

        // 全体のスライスに行を追加する.
        lines = append(lines, lineInt)
    }
 
    if err := scanner.Err(); err != nil {
        fmt.Println(err)
    }

    return lines
}

func getMin(a, b int) int {
    if a < b {
        return a
    }
    return b
}