Problem117 赤タイル, 緑タイル, そして青タイル

問題

黒い正方形のタイルと, 2ユニットの長さの赤のタイル,
3ユニットの長さの緑のタイル, 4ユニットの長さの青のタイルから選んで組み合わせて,
5ユニットの長さの1列をタイルで敷く方法はちょうど15通りある.



長さ50ユニットの1列をタイルで敷く方法は何通りあるか.

ソース

using System;

class Program
{
    //const int Unit = 5;
    const int Unit = 50;

    static void Main()
    {
        //場合の数[残りのマス]なDP表
        long[] DPArr = new long[Unit + 1];
        DPArr[Unit] = 1;

        for (int I = Unit; 1 <= I; I--) {
            if (DPArr[I] == 0) continue;

            Action<int> UpdateAct = (pLen) =>
            {
                int NewI = I - pLen;
                if (NewI >= 0) DPArr[NewI] += DPArr[I];
            };

            UpdateAct(1); //黒タイルを使う場合
            UpdateAct(2); //赤タイルを使う場合
            UpdateAct(3); //緑タイルを使う場合
            UpdateAct(4); //青タイルを使う場合
        }
        Console.WriteLine("解は{0}通り", DPArr[0]);
    }
}

実行結果

解は100808458960497通り

解説

動的計画法で解いてます。