day 37 | 贪心完全背包

昨天的01 背包求解的是三类问题，

在空间和为space的限制下求

1. 求放入物品的最大的价值
2. 求装满背包的方法数量
3. 求背包最大可以放的物品数量

01背包的一维空间遍历顺序必须是从大到小。 否则这一轮的便利结果会覆盖上一轮的。

在从大到小的便利顺序要求下，必须是遍历物品类型在外，空间在内。 否则dp[s-space[i]]的结果恒为初始值，是没有更新到的。

完全背包要求可以多次放入物品，此时空间遍历是要从小到大的。因为需要考虑同一个物品放多次的情况。

既然是从小到大的空间顺序，就可以先遍历空间再遍历物品了。此时要区分的是两种遍历内外顺序的区别。

• 先遍历物品种类，再遍历空间。 此时物品种类是有序的，所以遍历的方法数量是组合数量
• 先遍历空间，再遍历物品种类。 此时会对每一个位置上的遍历所有种类，方法数量是排序的数量。

然后对今天的求解问题归纳一下。

518. 零钱兑换 II

• 空间和的情况下的方法组合数量

377. 组合总和 Ⅳ

• 空间和的情况下的方法排序数量

70. 爬楼梯

• 空间和的情况下的方法排序数量