プロジェクトオイラー問31

Problem 31 「硬貨の和」 †

イギリスでは硬貨はポンド£とペンスpがあり，一般的に流通している硬貨は以下の8種類である.

1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).

以下の方法で£2を作ることが可能である．

1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p

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

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2031


解法
今回はＣ++
動的計画法で多めに見積もってもＢｉｇＯ（8*200）
Ｐｒｏｌｏｇで素朴な動的計画法な実装をすると深さ優先で全探索したほうが速くなるかもしれないのでＣ++とした。

#include<stdio.h>
int main(){
int dp[201]={0},coins[]={1,2,5,10,20,50,100,200};
dp[0]=1;
for(int j=0;j<8;j++){
int coin=coins[j];
for(int i=coin;i<=200;i++){
dp[i]+=dp[i-coin];
}
}
printf("%d\n",dp[200]);
}