凑单后续，女朋友说商品购买不限数量……
假设这次的优惠是满100-30，我们要凑够100块钱的商品，女朋友收藏夹的商品有四个，标价分别是 10，50，45，100。那么共有几种凑单方案呢？
这么简单的问题，我们先来用手算一下：
100 = 100 100 = 50+50 100 = 50+10+10+10+10+10 100 = 45+45+10 100 = 10+10+10+10+10+10+10+10+10+10
这总共有 5 种凑单方法，正好可以凑够100块钱。
emmmm……那么今天的凑单文章到此结束……
这可不行，后天女朋友准备凑单一千，那可咋整啊？
我们来科学的分析一下这个问题，面对这样的问题，该从哪里下手呢？
从上次的凑单的问题，我们可以看到一个物品有两个状态，加入购物车和不加入购物车。但是这一次，多了一条：不限数量，那么还能套用上次的解法吗？
在套娃之前，我们可以使用暴力解法，遍历所有的可能性，把所有的可能都列举出来，但是暴力面对这种不限数量的操作，怕是有点难搞哦。
现在我们来把这个问题转化一下，转化成选不选当前商品的操作，先用一些变量表示一下这些需要用的东西。
优惠券的最低限制金额记为 amount
收藏夹的商品记作goods[i]，i表示第几个商品，goods[i]中存放的值表示商品的价格。
假如我们把第 i 件商品加入购物车，然后购物车的金额变成了total，那么购物车的金额满足total的方案数量就变成了原来总金额已经到达total的数量和那些加上第 i 件商品的价值以后达到的total的方案数量之和。
转化成状态方程式就是
total金额方案数 = 历史total金额方案数 + (total-goods[i])金额方案数
状态转移方程可以列出来的话，那么就很容易做计算了，最后的优惠券金额方案数就是我们需要的值，我们只要往前递推就可以了。
我们不需要关注(total-goods[i])金额的方案组合是什么样子，是否包含当前商品。
这里有一点，购物车金额的变化中，大金额方案的数量计算依赖于小金额方案的数量，所以购物车的金额要从小往大计算。
这里有一点需要注意，我们这里只考虑了商品的价格，没有考虑相同价格的不同商品，所以goods[]中没有重复值出现，这一点也很重要
状态转移方程再怎么转移都需要有一个起始点，所以我们要找到临界点，那么这个临界点是什么呢？
让时间回到最起始点，当你的女朋友刚打开购物APP时，购物车的总金额最低为0，这时候有几种方案呢？
只有一种，那就是什么商品都没选，这个也就是临界点。
大部分操作都已经明确了，我们把这整个过程转化成代码
参考代码
public int shop(int amount, int[] goods) { int len = goods.length; // 状态记录数组，记录不同购物车金额下的组合数量 int[] status = new int[amount + 1]; // 购物车金额为0时的方案数量 status[0] = 1; for (int j = 0; j < len; j++) { int money = goods[j]; if (money > amount) { continue; } for (int k = money; k <= amount; k++) { // 方案数量的状态转移方程 status[k] = status[k] + status[k - money]; } } return status[amount]; }
同学们，你以为这样就可以优雅结束了吗？
不，这才是个开始。
留下两个小问题，思考一下：
- 如果存在相同价格的不同的商品，那么该怎么计算方案数量？
- 如果女朋友在计算过程中增删收藏夹的商品，那么这又该怎么计算方案数量呢？
