算法回忆录：母函数解决整数拆分_整数拆分 母函数

省略了很多内容，所以需要一定基础才可阅读。主要为了说清母函数如何解决此问题。
整数拆分:
1、整数拆分可以理解为苹果放盘子问题（把N个苹果放在M个盘子里有多少种方法），只是这是相当于把N个苹果放在N个盘子里而已。
代码：

    int zh(int n,int m)
    {
        if(n==1 || m==1)
            return 1;
        if(n <= m)
            return (1 + zh(n, n-1));

        return zh(n, m-1) + zh(n-m, m); 
    }
1
2
3
4
5
6
7
8
9

2、整数拆分同样可以用递推解决，其实这同样用到了递归所得的关键函数关系： f(n, m) = f(n, m-1) + f(n-m, m)。

    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n;j ++){
            if(i <= j){
                ans[j] += ans[j-i];
            }
        }
    }
1
2
3
4
5
6
7

3、用母函数解决： 这才是本文的关键。
a、首先要理解为什么整数拆分可以用G(x)=(1+x+x^2+x^3+x^4+……)(1+x^2+x^4+x^6)(1+x^3+x^6+x^9+……)(1+x^4+x^8+x^12+……)……表示。这个可以这样理解：第一项可以理解为用1来拆分，假使要求x^7的系数，那么第一个多项式中的x^7就是由7个x相乘得出的（7=1+1+1+1+1+1+1），除此之外第一个多项x^2可以与后面的多项式中的x^5相乘得出，这个可以理解为7=1+1+5。但是第2项的表达式中x^2*后项中x^5就是7=2+5。这个逻辑必须理解，这是G（x）解决整数拆分的关键思想。
b、如何理解代码？ 循环的控制很难理解：但是大体可以这样解释：显然c1存储变量，c2为临时变量；执行一次i循环，c2则表示乘到当前多项式x的n次幂的系数为c2【n】，然后c2赋值到c1，c2初始化，继续执行。

    while (cin>>n) {
        for (i=0; i<=n; i++) { c1[i]=0; c2[i]=0; }
        for (i=0; i<=n; i++) c1[i]=1;

        for (i=2; i<=n; i++) {
            //key code
            for (j=0; j<=n; j++) {
                for (k=0; k+j<=n; k+=i) {  
                    c2[j+k] += c1[j];  
                }
            }

            for (j=0; j<=n; j++) { 
                c1[j] = c2[j];  c2[j] = 0;  
            }
        }
        cout<< c1[n] <<endl;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18