hdu 1284 钱币兑换问题 （DP）
点击打开链接
//hdu 1284 找规律 //给出n 看能n 内有多少个 2 和多少个3 //具体看代码和一下注视#include<stdio.h> #include <string.h> #define N 35000__int64 ans[N];int main(){ int n; // 计算i 可以由多少个 2 组成 for(int i = 0; i < N; ++i)// 后面的 +1 表示全由1组成的(只有1中情况)ans[i] = i / 2 + 1; //则这一行表示由 2组成的情况加上由1组成的情况 // 从前面往后推,看能由几个3 组成,比如 ans[3]表示钱为3时 // 由1,2分硬币组成的情况,可以表示成钱为0 时加上一个3分硬币(这时方法数为// 钱为 0 时由1,2,3组成的情况 加上钱为3时由1,2组成的方法数)// 因此 ans[i] += ans[i-3]+1;不需要后面的+1 for(int i = 3; i < N; ++i) ans[i] += ans[i-3];//这一行ans[i]就表示由2组成的情况加上由3组成的情况 // ans[6]就相当于由2组成的情况ans[6] 加上 由1,2,3组成的情况的ans[6-3] // 这样往后推，就可以把 由3分组成的情况加上去 while(scanf("%d", &n) != EOF) printf("%I64d\n", ans[n]);return 0; }