UVa 674 - Coin Change
时间：2011-06-15 来源：wangzhuo
动态规划：
只有价值为1的金币时，构造所有值的方法数均为1;
由1,5构造时，dp[i]+=dp[i-5],及构造i的方法=(原来只由1构造的方法数)+(由1,5构造i-5的方法数);
由1,5,10构造时，堆排dp[i]+=dp[i-10],构造i的方法=原来只由1,5构造的方法数+由1,5,10构造i-10的方法数;
......dp[i]+=dp[i-25]......;
......dp[i]+=dp[i-50]......;
View Code
View Code
1 #include "iostream"
2 #include <stdio.h>
3 using namespace std;
4 int dp[7490];
5 int coin[5]={1,5,10,25,50};
6
7 int main()
8 {
9 dp[0]=1;
10 for(int i=0;i<5;i++)
11 {
12 for(int j=1;j<7490;j++)
13 {
14 if(j>=coin[i])
15 dp[j]+=dp[j-coin[i]];
16 }
17 }
18 int cents;
19 while(scanf("%d",¢s)==1)
20 printf("%d\n",dp[cents]);
21 return 0;
22 }
相关阅读 更多 +
排行榜 更多 +
