Problem Description
在一个国家仅有1分，2分，3分硬币，将钱N兑换成硬币有很多种兑法。请你编程序计算出共有多少种兑法。
Input
每行只有一个正整数N，N小于32768。
Output
对应每个输入，输出兑换方法数。
Sample Input
2934
12553
Sample Output
718831
13137761
母函数暂时不会，只能用背包做，dp[i][j]表示使用前i种钱换成j的总共方式。首先要考虑初始问题，dp[i][0]=1；有再多的钱换成0元只有一种方式。dp[1][a[1]* q]=1; 这个表示第一种钱的倍数有一种方式，比如表示第一种钱是3块的时候，dp[1][3]表示一张三块，dp[1][3*2]表示6块钱刚好可以用两张三块钱表示。
正常情况下的核心状态转移方程为
if(i>j) {dp[i][j]=dp[i-1][j];}无法使用第i种钱，就是使用i-1种钱抓取j的方式数
else {dp[i][j]=dp[i-1][j] dp[i][j-a[i]];}可以使用第i张，总个数就是不适用第i种的加上使用第i种的，不使用第i种就是dp[i-1][j]，使用了i种就是dp[i][j-a[i]];其实这里有一个递归/调用自己的过程，使用了一张后dp[i][j-a[i]]在重新判断这个数能否使用i，如果能使用，再次拆分，一直拆到最后无法使用i为止。
附上代码：
import java.util.Scanner; /* * 找零钱问题背包问题 */ public class 杭电1284 { public static void main(String[] args) { Scanner sc=new Scanner(System.in); int dp[][]=new int[4][32768]; for(int i=1;i<4;i ) {dp[i][0]=1;} for(int j=1;j<32768;j ) {dp[1][j]=1;}//这里a[i]刚好为i所以a[1]=1;可以简化不用数组 for(int i=1;i<4;i ) { for(int j=1;j<32768;j ) { if(i>j) {dp[i][j]=dp[i-1][j];} else dp[i][j]=dp[i-1][j] dp[i][j-i];//a[i]=i;就一分，两分，三分。 } } while(sc.hasNext()) { int n=sc.nextInt(); System.out.println(dp[3][n]); } } }
希望后面学了母函数能够在用母函数写出来！
更新母函数代码,直接套模板即可
import java.util.Scanner; public class hdu1284 { static long c1[]; static long c2[]; public static void main(String[] args) { Scanner sc=new Scanner(System.in); c1=new long[32769]; c2=new long[32769]; sovle(32768); while(sc.hasNext()) { int t=sc.nextInt(); System.out.println(c1[t]); } } private static void sovle(int n) { // TODO 自动生成的方法存根 for(int i=0;i<=n;i ) { c1[i]=1; c2[i]=0; } for(int i=2;i<=3;i ) { for(int j=0;j<=n;j ) { for(int k=0;k j<=n;k =i) { c2[k j] =c1[j]; } } for(int j=0;j<=n;j ) { c1[j]=c2[j];c2[j]=0; } } } }
