通学路（動的計画法）

void calc(void)
{
    int t[17][17] = {};
    for (int j=1;j <= a;j++) {
        for (int k=1;k <= b;k++) {
            if (j==1 && k==1)
                t[k][j] = 1;
            else if (point[k][j] == 1)
                t[k][j] = 0;
            else
                t[k][j] = t[k][j-1] + t[k-1][j];
        }
    }
    m = t[b][a];
}

mainはさっきの記事と同じ

動的計画法ってよく出てくるんですけど、使いこなせていないのが現実orz

数学的な思考が足りてませんかそうですか

再帰の場合は計算量が抜群に増えていきますが、動的計画法ではそれほど気になりません。

5番目の一番大きい入力ファイルで時間を測ってみたところ

再帰　：　500ミリ秒

動的　：　0ミリ秒

圧倒的といえば圧倒的ですね。

5番目のファイルの先頭を16 16から19 19に変更するとさらに差が広がります。再帰だと10秒以上かかりますが、動的計画法だと数ミリ秒で終わります。この差はデカイ！