Problem31 2ポンドを作る組み合わせの数

問題

イギリスでは硬貨はポンドとペンスがあり，一般的に流通している硬貨は以下の8種類である.
1ペンス, 2ペンス, 5ペンス, 10ペンス, 20ペンス, 50ペンス, 1ポンド (100ペンス),2ポンド (200ペンス).

以下の方法で2ポンドを作ることが可能である．
1×1ポンド + 1×50ペンス + 2×20ペンス + 1×5ペンス + 1×2ペンス + 3×1ペンス

これらの硬貨を使って2ポンドを作る方法は何通りあるか?

ソース

using System;

class Program
{
    static void Main()
    {
        //場合の数[合計金額]なDP表
        int[] DPArr = new int[200 + 1];
        DPArr[0] = 1;
        int UB = DPArr.GetUpperBound(0);

        foreach (int EachInt in new int[] { 1, 2, 5, 10, 20, 50, 100, 200 }) {
            for (int I = 0; I <= UB; I++) {
                if (DPArr[I] == 0) continue;

                int NewInd = I + EachInt;
                if (UB < NewInd) break;
                DPArr[NewInd] += DPArr[I];
            }
        }
        Console.WriteLine(DPArr[UB]);
    }
}

実行結果

73682

解説

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