杭电1284钱币兑换问题—背包dp/母函数(java)

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]);
	 }
	} }

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
 

希望后面学了母函数能够在用母函数写出来！
更新母函数代码,直接套模板即可

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; }
		} }

}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
 

文章来源: bigsai.blog.csdn.net，作者：Big sai，版权归原作者所有，如需转载，请联系作者。

原文链接：bigsai.blog.csdn.net/article/details/79646194