钱币兑换问题
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 6296 Accepted Submission(s): 3640
Problem Description 在一个国家仅有1分，2分，3分硬币，将钱N兑换成硬币有很多种兑法。请你
编程序计算出共有多少种兑法。
Input 每行只有一个正整数N，N小于32768。
Output 对应每个输入，输出兑换方法数。
Sample Input
2934
12553
Sample Output
718831
13137761
状态转移方程：dp[i][j] = dp[i-1][j]+dp[1][j-(1~3)] (d[0][0] = 1);
代码：
#include
#include
#define MAX 35000 int dp[MAX] ; int main() { int n; while(scanf("%d",&n) != EOF) { memset(dp,0,sizeof(int)*(n+10)) ; dp[0] = 1 ; for(int i = 1 ; i <= 3 ; ++i) { for(int j = i ; j <= n ; ++j) dp[j] = dp[j]+dp[j-i] ; } printf("%d\n",dp[n]) ; } return 0 ; }
呵呵，，再附送你们一个神代码(不是我写的)：
#include
int main()
{
int n,sum,i;
while(scanf("%d",&n)!=EOF)
{
int t=n/3+1;//3分的个数
sum=0;
for(i=0;i
因为本题的钱币数只有1,2,3三种，所以令t=n/3，然后遍历一遍i从0到t，代表面值为三分的个数，然后用总价值减去三分硬币所代表的价值，用这个值除以2，得到的数就是每确定一个三分的数值后对应的2分的硬币的兑换总数。最后再加上全部为1分的情况，就是所求的解了。
下面的代码简直是碉堡了。