算法回忆录：母函数解决整数拆分 - xhpakill - SegmentFault

算法回忆录：母函数解决整数拆分 - xhpakill - SegmentFault

省略了很多内容，所以需要一定基础才可阅读。主要为了说清母函数如何解决此问题。
整数拆分:
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);          }

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

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;

Read full article from 算法回忆录：母函数解决整数拆分 - xhpakill - SegmentFault