1. 解法一：生成函数
1.1 思路
（由于公式有点多，但是耐心看下去你会发现没你想象中那么难懂这些公式，谢谢！）
看到好些大佬都提到此题可以用生成函数解，那么我们先了解一些关于生成函数（Generating function）的基础知识。首先看定义：
- 专业地术语解释：在数学中，某个序列
的母函数（又称生成函数，英语：Generating function）是一种形式幂级数，其每一项的系数可以提供关于这个序列的信息。
- 通俗地解释：就是对于从
到
这样一个序列，我们可以构造一个关于
的多项式函数
,使得
此时这个的生成函数。其中 函数第
项前面的系数
PS：
那么问题来了，这个生成函数有何作用？
可以解决一些组合、排列的数学问题。（注：本文此处主要谈论的是普通生成函数）
这里看一个很经典的砝码案例：
若有1克、2克、3克、4克的砝码各一枚，能称出哪几种重量？各有几种可能方案？
这里我们用 表示砝码，
的指数表示砝码的重量，所以
1克砝码的生成函数可以表示为：
（注：这里的 1实际上是的简化写法，表示1克的砝码取0个，所以整个生成函数表示👉1克的砝码有两种状态，即 取或 不取。）
2克砝码的生成函数可以表示为：
3克砝码的生成函数可以表示为：
4克砝码的生成函数可以表示为：
然后将上面的4个生成函数相乘，得到一个新的生成函数：
此时的指数就表示能称出的砝码重量种类，前面的系数就是对应的方案数。
比如称出5克的方案有2种，而称出8克的方案就1种。
那么回到本题，是不是发现题目的描述跟上面的砝码问题很像，所以我们也可以用生成函数来解此题：
首先第一个盘子里有无限个面包🍞，那么它的取法就是无限个，对应的生成函数就可以写成：
=
接着第二个盘子里只有1个面包🍞，所以取法就1种，生成函数如下：
=
同理可以得到第三个盘子只有4个面包🍞的生成函数：
=
第四个盘子无限个面包🍞，但是只能两个两个的拿，所以生成函数如下：
=
第五个盘子也是无限个面包🍞，也是只能5个5个的拿，那么生成函数如下：
=
由于直接把上面5个生成函数相乘后表达式相当的复杂。。。所以这里需要简化一下上面的5个生成函数，仔细看第一个盘子的生成函数： =
，有没有觉得很眼熟🤔？这不就是一个无穷等比数列的求和式子吗？！那么当
，等比数列求和可得到
。
所以 =
，同理可以化简其他四个生成函数如下：
=
=
=
=
现在我们再次把这5个简化后的生成函数相乘：
最后可以得到新的生成函数👉
但是到这里我们还是得不到想要的答案。。。
所以还需要再次变换一下这个表达式，这里又要补充一个知识点👉牛顿广义二项式定理：
当 =
的时候：
接着我们再次变换一下，用 换掉
：
然后你会惊奇地发现？！前面地系数
不就是组合数嘛？不过是分子前面有负号！
（PPS: 再次补充组合数👇公式
=
=
）
同理就可以变换
=
=
于是我们就得到了最终地生成函数转化后地式子：
所以面包🍞最后生成函数因为指数
，所以
因此最后的挑选方案面包数就是 前面地系数 
又因为，所以最后的答案就是右边👉的等式。
1.2 核心代码
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# @param n int整型
# @return long长整型
#
class Solution:
def wwork(self , n ):
# write code here
#通过找规律和生成函数变换最后得到f(n) = ((n+1)*(n+2))//2
return ((n+1)*(n+2)) // 2 1.3 复杂度分析
- 时间复杂度：
(直接套用公式)
- 空间复杂度：
------------------------------------------------------我是超短的解法二分割线----------------------------------------------
2. 解法二：math库
2.1 思路
根据上面解法一我们已经得到了方案数为，
由于Python从3.8版本开始，math库就添加了组合数的解决函数方法：
所以这里我们可以直接使用Python的数学库方法 math.comb(n,k)来解决。
2.2 核心代码
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# @param n int整型
# @return long长整型
#
import math
class Solution:
def wwork(self , n ):
# write code here
#直接使用组合数的解决函数
return math.comb(n+2, n)2.3 复杂度分析
- 时间复杂度：
- 空间复杂度：
京公网安备 11010502036488号