トップページに戻る
次のC#のサンプルへ
前のC#のサンプルへ
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
解説
動的計画法で解いてます。