Q17 30人31脚に挑戦！

C#のソース

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        //1人の場合は、男、女で2通り
        //2人の場合は、男男、男女、女男で3通り
        //3人の場合は、最初が男なら2人の場合の数
        //             最初が女なら1人の場合の数

        var CntDict = new Dictionary<int, int>();
        CntDict[1] = 2;
        CntDict[2] = 3;
        for (int I = 3; I <= 30; I++) {
            CntDict[I] = CntDict[I - 1] + CntDict[I - 2];
        }

        Console.WriteLine(CntDict[30]);
    }
}

実行結果

2178309

解説

漸化式を求めて解いてます。