降维打击面试题系列:生成函数(一)

先看几道经典面试题:

给定若干种数量不限的硬币的币值,编写代码计算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个水果,苹果只能拿奇数个,香蕉只能拿偶数个,至少要拿一个梨,求问有多少种选取方法?

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

  • 苹果:1,3,5
  • 香蕉:0,2,4
  • 梨:1,2,3,4,5

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

  • 1, 0, 4
  • 1, 2, 2
  • 3, 0, 2

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

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

(x+x3+x5)(x0+x2+x4)(x+x2+x3+x4+x5)(x+x^3+x^5)(x^0+x^2+x^4)(x+x^2+x^3+x^4+x^5)

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

手工计算嫌麻烦的话,可以借助工具:

www.wolframalpha.com/input?i=%28…

x14+x13+3x12+3x11+6x10+5x9+7x8+5x7+6x6+3x5+3x4+x3+x2x^{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+x3+x5+...)(x0+x2+x4+...)(x+x2+x3+x4+x5+...)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+x3+x5+...F(x) = x+x^3+x^5+…

这是一个无穷的级数,我们把它两边乘以

x2x^2

试试看:

x2F(x)=x3+x5+...x^2F(x) = x^3+x^5+…

我们再把它与原来的等式相减,得到:

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

稍微化简得到:

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

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

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

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

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

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

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

www.wolframalpha.com/input?i=%5C…

G(x)=x1x211x2x1x=n=0116xn(1+(1)n+2(1+(1)n)n+2n2)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(-1)^n

用取余运算(%)代替,改写成JS代码:

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

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

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

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

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

(0)
上一篇 2023年5月3日 上午10:10
下一篇 2023年5月3日 上午10:20

相关推荐

发表评论

登录后才能评论