一、题目

       小明几乎每天早晨都会在一家包子铺吃早餐。他发现这家包子铺有N种蒸笼，其中第i种蒸笼恰好能放Ai个包子。每种蒸笼都有非常多笼，可以认为是无限笼。每当有顾客想买X个包子，卖包子的大叔就会迅速选出若干笼包子来，使得这若干笼中恰好一共有X个包子。比如一共有 3 种蒸笼，分别能放 3、4 和 5 个包子。当顾客想买 11 个包子时，大叔就会选 2 笼 3 个的再加 1 笼 5 个的（也可能选出 1 笼 3 个的再加 2 笼 4 个的）。当然有时包子大叔无论如何也凑不出顾客想买的数量。比如一共有 3 种蒸笼，分别能放 4、5 和 6 个包子。而顾客想买 7 个包子时，大叔就凑不出来了。小明想知道一共有多少种数目是包子大叔凑不出来的。
        如果凑不出的数目有无限多个，输出 INF。

二、数学知识前提

裴蜀定理：

        对任何整数a、b和它们的最大公约数d，关于未知数x和y的线性不定方程（称为裴蜀等式）：若a,b是整数,且gcd(a,b)=d，那么对于任意的整数x,y,ax+by都一定是d的倍数，特别地，一定存在整数x,y，使ax+by=d成立。

       该定理也可以拓展到多个整数。同时在本题中要求如果凑不出的数目有无限多个，输出 INF。由定理可知，对于几个整数组合来说，他们能够组合出来的数一定是d的倍数，如果这个d是1，那么在此基础上能组合出任意数（当然由于x，y在本题中也是整数，所以还是有组合不出来的数），反之则只能组合出d的倍数，即有无限个凑出来的数

三、解题思路

       题目是有N个包子笼来组合，是一个完全背包的变种，所以用完全背包来做，首先检测是否有无限个凑不出来的，即采用最大公约数来检测。为了方便理解，存储笼子数组A[i]时多加一个并将A[0]弃用，这样i就代表第i种笼子。dp[i][j]数组采用bool类型，用来表示能否凑出来，行数为笼子种类数，列数尽量多，设为10000，代表需求的包子数。

四、状态转移

初始的时候全部为0（false），并且易知在没有任何笼子的时候，什么数也拼不出来，即i=0时的那一行全部为0，而且在需求为0的情况下，全都可以凑出来，即j=0那一列全为true（dp[0][0]=true）.

打出表来，分析可知一种情况是在上一行已经可以拼出来的情况，此时在这一行也可以拼出来。还有一种情况是上一行拼不出来，这时如果在第j列(即需求j个包子)的情况下减去k倍（k=1，2，3......）这一行代表的笼子包子数（A[i]）可以凑出来那么这个情况下也可以凑出来。方程表达为

由于dp[i][j-A[i]]=dp[i][j-2A[i]]······dp[i][j-kA[i]]，可以发现后面的式子都可以这样表示，即如果dp[i][j-A[i]]可以，那后面的式子中至少有一个可以，如果dp[i][j-A[i]]不可以，那么后面式子也不必考虑，必定都不可以，所以可以化简为

还有就是j-A[i]<0时，那肯定是false，综合起来代码如下

上述是我自己的理解，但是感觉还有点不对劲，所以我再写一个别人写的理解方式，比较偏向证明。

因为顺序循环，在本行执行dp时，上一行已经完成，所以本行dp[i][j]可表示为如下

另外由于

观察上述两式可发现有重叠，所以可得

综合起来代码与刚才一样。

dp完成之后，就可以在行数为N的那一行循环数出false的个数即为答案。

五、完整代码

六、出现问题

对于动态规划、01背包，完全背包还是不太理解，需要继续强化。

七、参考资料