Original

Starting in the top left corner of a 22 grid, there are 6 routes (without backtracking) to the bottom right corner.

How many routes are there through a 2020 grid?

和訳

2 × 2 のマス目の左上からスタートした場合、引き返しなしで右下にいくルートは 6 つある。

では、20 × 20 のマス目ではいくつのルートがあるか。

当てにならないソースコード(C#)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
using System;

namespace ProjectEuler {
    class Problem15 {
        const int width = 20, height = 20;
        long[,] table = new long[width+1, height+1];
        public Problem15() {
            Console.WriteLine(this.ToString());
            Console.WriteLine("> " + RouteCount(width, height));
        }
        long RouteCount(int w, int h) {
            if (table[w, h] == 0) {
                table[w, h] += (w == 1) ? 1 : RouteCount(w - 1, h);
                table[w, h] += (h == 1) ? 1 : RouteCount(w, h - 1);
            }
            return table[w, h];
        }
    }
}


RouteCount(a, b) と RouteCount(b, a) の値が同じであることを利用すれば
さらに高速＆メモリ節約になります。
コード量は増えますが。