凑单后续，女朋友说商品购买不限数量……

假设这次的优惠是满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];
}

同学们，你以为这样就可以优雅结束了吗？

不，这才是个开始。

留下两个小问题，思考一下：

1. 如果存在相同价格的不同的商品，那么该怎么计算方案数量？
   
2. 如果女朋友在计算过程中增删收藏夹的商品，那么这又该怎么计算方案数量呢？