描述

这是一篇面对初级coder的题解。
知识点：生成函数（母函数） 动态规划（背包问题）
难度：四星

题解

自助餐厅里有5个盘子，里面装的都是面包。

第1个盘子里有无限个面包；

第2个盘子里只有1个面包；

第3个盘子里只有4个面包；

第4个盘子里也有无限个面包，但必须两个两个地拿；

第5个盘子里也有无限个面包，但必须5个5个地拿；

给定正整数n，求有多少种正好拿出n个面包的方案。

方案a和方案b不同，当且仅当方案a存在从某个盘子里拿出面包的数量与方案b中对应盘子拿出的数量不同。

分析：这道题乍看和跳台阶的动态规划有些类似 但是那个是排列 这个是组合

方法一：动态规划

参考 https://blog.nowcoder.net/n/e276b6459eb44c41a5e87a764dd354f9

记表示用前个盘子凑出总数为的方案数量，

初始时，因为每个盘子面包的数量有限，我们要枚举每一个出现的可能数量。

则记第i个盘子使用了k个，用前面的数组去推算后面的方案个数

dp[i+1][j+k*a[i][0]] += dp[i][j]

约束条件为
  和

class Solution {
public:
    long long wwork(int n) {
        int a[5][2]={{1,n},{1,1},{1,4},{2,n/2},{5,n/5}};//定义每个盘子里面包的拿法和数量（最大值）
        vector<long long> dp(n + 1, 0);
        dp[0]=1;//初始化
        for(long long i = 0; i < 5; i++){ //遍历5种货币
            for(long long j = n; j > 0; j--){ //遍历0~j面包总数
                for(long long k = 1; k <= a[i][1]; k++){ //枚举第i个盘子里面包的个数
                    if(j-k*a[i][0] >= 0) //未达上限
                        dp[j]+= dp[j-k*a[i][0]];//递归·
                    else
                        break;
                }
            }
        }
        return dp[n];
    }
};

运行测试：
3/10 组用例通过 超时
运行时间1001ms

时间复杂度：，整体逻辑采用了三重循环 k是最大的面包个数

空间复杂度：，即为dp矩阵的大小，除此之外无额外空间

方法二：生成函数

生成函数(母函数)什么是生成函数：wiki上的介绍在数学中，某个序列(的母函数（又称生成函数，英语：Generating function）是一种形式幂级数，其每一项的系数可以提供关于这个序列的信息。使用母函数解决问题的方法称为母函数方法。

母函数可分为很多种，包括普通母函数、指数母函数、L级数、贝尔级数和狄利克雷级数。对每个序列都可以写出以上每个类型的一个母函数。构造母函数的目的一般是为了解决某个特定的问题，因此选用何种母函数视乎序列本身的特性和问题的类型。

母函数，又称生成函数，是ACM竞赛中经常使用的一种解题算法，常用来解决组合方面的题目。
生成函数的定义：

生成函数的定义： 称 是序列的生成函数

对于本题：

生成函数是一个等比数列，其通项公式为

第1个盘子里有无限个面包：对应的生成函数为：

第2个盘子里只有1个面包，对应的生成函数为：

3：有四个，对应的生成函数为

4：无限但只能取偶数个，对应的生成函数为

5：无限但只能取)的倍数个，对应的生成函数为

当n趋于无穷大时，所求答案为将以上五个生成函数相乘，得到最后的生成函数为

所求第n项的值为：

class Solution {
public:
    long long wwork(int n) {
        long long n1=n+1;
        long long n2=n+2;
        return n1*n2/2; //按long long 计算
    }
}; 

显然，这样直接采用数值计算，时间复杂度和空间复杂度都为

总结

总结一下，生成函数大多用来解决有限或无限物体的组合方案。

各个组合的生成函数相乘即可