降维打击面试题系列：生成函数（一）

先看几道经典面试题：

给定若干种数量不限的硬币的币值，编写代码计算n分有几种表示法。

青蛙跳台阶问题：一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

凑钱问题比较常见的解法是动态规划，时间复杂度O(mn),m为硬币种类,空间复杂度O(n)。

青蛙跳台阶问题可以转化成斐波那契数列，有时也会被当做动态规划的例子，常见解法时间复杂度O(n)，空间复杂度O(1)。

这几个题看上去没有任何相关性，但有一种数学工具却能够为它们提供统一的解决方案，那就是生成函数。

生成函数英文是 Generating Function，有时也会被翻译成母函数，它是一种重要的组合数学方法。

生成函数不但能为这些多样的问题提供统一思路，还能提供超过面试官期望的时间复杂度，可以把凑钱问题的时间复杂度降低到 O(k * log(n))，空间复杂度为 O(1)，把青蛙跳台阶问题时间复杂度降低到 O(log(n))。

我们先从一个最简单的问题出发，了解生成函数。

有苹果，香蕉和梨三种水果，现在要选取5个水果，苹果只能拿奇数个，香蕉只能拿偶数个，至少要拿一个梨，求问有多少种选取方法？

先来看看一般解法，我们考虑每种水果可以选取的数量：

我们从每行中，选取一个数字，组成一种情况，再计数其中和为7的情况即可。最终我们得到：

共三组可行解，所以答案为有3种选取方法。

这里我们注意到一个事实，当我们对苹果和香蕉和梨进行组合时，与多项式乘法非常类似。如果我们把水果数量写作多项式某项的系数

(x+x^3+x^5)(x^0+x^2+x^4)(x+x^2+x^3+x^4+x^5)

相乘展开后，就可以根据特定项的系数知道选取方法数。

手工计算嫌麻烦的话，可以借助工具：

x^{14} + x^{13} + 3 x^{12} + 3 x^{11} + 6 x^{10} + 5 x^{9} + 7 x^{8} + 5 x^{7} + 6 x^{6} + 3 x^{5} + 3 x^{4} + x^{3} + x^{2}

我们看到，其中5次项的系数为3，即选取5个水果共有3种方法，与我们前面的计算一致。

我们把这一个多项式称作这一组合问题的“生成函数”，但是到此为止，我们并没有感受到生成函数给我们的解题带来了什么方便，若以算法角度来看，这样的解法也是时间复杂度十分糟糕。

但是，生成函数为我们构建了组合问题和代数问题的一道桥梁，转化成代数问题之后，我们就可以使用高等数学中的一系列“科技与狠活”。

因为这里的多项式中，我们完全无需关心x的具体类型和取值，x本身也没有实际的意义，所以生成函数也被叫做形式幂级数。

接下来，我们升级一下题目，借此来体验一下生成函数的威力。

有苹果，香蕉和梨三种水果，现在要选取n个水果，苹果只能拿奇数个，香蕉只能拿偶数个，至少要拿一个梨，求问有多少种选取方法？

当水果数量升级到n，我们的生成函数变成了：

G(x)=(x+x^3+x^5+…)(x^0+x^2+x^4+…)(x+x^2+x^3+x^4+x^5+…)

因为我们不确定n的范围，我们的生成函数的每一个乘数都变成了无穷。我们当然还可以把次数限制在n以内，但是这样计算这个幂级数展开的计算量也相当巨大，并不是一个好的方法。

我们取出其中一个来研究一下：

F(x) = x+x^3+x^5+…

这是一个无穷的级数，我们把它两边乘以 $x^2$ 试试看：

x^2F(x) = x^3+x^5+…

我们再把它与原来的等式相减，得到：

(1-x^2)F(x) = x

稍微化简得到：

F(x) = \frac{x}{1-x^2}

你看，这个无穷的幂级数，反而比有限的情况表达起来更简洁。

我们对另外两个乘数项也如法炮制，可以得到：

G(x)=\frac{x}{1-x^2}*\frac{1}{1-x^2}*\frac{x}{1-x}

好了，这下简单是简单了，但是我们如何把这个东西变成多项式呢？

这就要用到大学里高等数学的知识了，不知道大家有没有忘记（或者根本就没学会？[doge]），我们可以使用泰勒级数将任意函数表示成多项式的形式，x=0处的泰勒级数又被称作麦克劳林级数。

麦克劳林级数具体怎么求……其实这么复杂的东西我也不太会，但是好在这个求法有固定的套路，我们直接求助wolframalpha即可。

G(x)=\frac{x}{1-x^2}*\frac{1}{1-x^2}*\frac{x}{1-x} =\sum_{n=0}^∞\frac{1}{16}x^n(-1+(-1)^n+2(1+(-1)^n)n+2n^2)

我们根据自己的理解，把 $(-1)^n$ 用取余运算(%)代替，改写成JS代码：

const f = n => (2 * n * n + (n % 2 ? -2 : 4 * n)) / 16

最终我们得到了这个问题 O(1) 的解答。

这里，我们看到，生成函数适用于多个独立要素组合的组合问题，我们可以通过乘系数后相减来化简无穷项形式幂级数，并且我们可以通过求麦克劳林级数强行算出生成函数的通项公式。

下一节我们来看看，如何利用生成函数如何处理递推关系。

原文链接：https://juejin.cn/post/7228522221341032508 作者：winter