プロジェクトオイラー問31 - sinapusu2002 @ ウィキ

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2031
Problem 31 「硬貨の和」 †
200ポンドを硬貨で作る。
何通りの作り方があるか？

if文がちょっとかっこ悪いですが動的計画法そのまま。

#include<stdio.h>
#include<string.h>

const int LIMIT=200;
int main(){
 	int dp[2][LIMIT+1];
	int coins[8]={1,2,5,10,20,50,100,200};
	int now,next;
	memset(dp,0,sizeof(dp));
	dp[0][0]=1;
	for(int i=0;i<8;i++){
 		now=i%2;
		next=(i+1)%2;
		int coin=coins[i];
		for(int j=0;j<=LIMIT;j++){
			if(j<coin){
				dp[next][j]=dp[now][j];
			}else{
 				dp[next][j]=dp[now][j]+dp[next][j-coin];
			}
		}
	}
	printf("%d",dp[next][200]);
}