雌函数法解决整数划分

母函数法解决整数划分

问题描述：把一个整数n划分成1到n的划分，例如3可以划分为1+1+1,1+2,3这三种划分，那么求n的划分数。

解题思路：

    可以把1，设为x的0次方：x^0

    把1，设为x的1次方：x^1

    .......把n，设为是x的n次方：x^n

    那么1可能出现，0,1,2,3,4,5,6...n次，而2可能出现0,1,2,3,.......n/2次，3可能出现0,1,2,3,4........n/3次等等。

   依照上面的把1可以表示成x^1:那么可能出现的次数就是1+x^1+2*x^1+3*x^1+...n*x^1,同理有1+1*x^2+2*x^2+.....(n/2)*x^2那么把这些多项式相乘起来，得

（1+1*x^1+2*x^1....n*x^1）(1+x^2+2*x^2....(n/2)*x^2).....(x^n)是不是x^n最终的系数就是n的整数划分数，下面是我的代码：

public class Main {

	public static int getNum(int n){
		//存放最终的结果
		int[] c1=new int[n+1];
		//存放当前两个多项式相乘的结果
		int[] c2=new int[n+1];
		//初始化让c1开始的系数全为1
		Arrays.fill(c1, 1);
		//初始化让c2开始的系数全为0
		Arrays.fill(c2, 0);
		for(int i=2;i<=n;i++){
		//i代表当前的x到底是多少次方
			for(int j=0;j<n+1;j++){
				//j代表从c1取出每个系数准备与当前多项式相乘
				for(int k=0;k+j<=n;k+=i){
					//k代表从当前x次方的多项式取出每一项然后，与c1里的多项式相乘
					c2[j+k]+=c1[j];
				}
			}
			//将c2存储的缓存结果放入c1
			for(int z=0;z<n+1;z++){
				c1[z]=c2[z];
				c2[z]=0;
			}
		}
		return c1[n];
	}
	public static void main(String[] args) {
		System.out.println(getNum(100));

	}

}