Project Euler 15

Problem 15

  • 2 次元配列の練習。
  • 20x20 なので 40 ステップで目的値に到達する。そのうち、水平移動は 20 ステップ行うので、40C20 を計算する方法でも良い。
  • 『組み合わせ入門』p.2
using System;

class PE015 {
    public static void Main() {
        const int N = 20;
        long[,] dp = new long[N+1, N+1];
        dp[0, 0] = 1;

        for (int i = 0; i <= N; i++) {
            for (int j = 0; j <= N; j++) {
                // 上から来るか
                long t = i > 0 ? dp[i-1, j] : 0;
                // 左から来るか
                long l = j > 0 ? dp[i, j-1] : 0;
                dp[i, j] += t + l;
            }
        }

        Console.WriteLine(dp[N, N]);
    }
}
  • N を 20 にするか、それとも 21 にするかで悩んだ。N=20 の方がわかりやすいのだが、配列の大きさを指定するときに N+1 とする必要がある。
  • C# には ジャグ配列 (C# プログラミング ガイド) というのもあり、異なるサイズの配列を格納できるみたい。