day38 | 动规

今天这类问题可以说是 再空间和的情况下，最大空间可以放的最少的物品数量。

• （目前遇到的背包问题可以求解四种问题最大值，最大数量,最小数量和方案数)

322. 零钱兑换

凑成总金额所需的 最少的硬币个数。 无所谓组合还是排序。 然后转移方程是min ，注意初始化的时候要取极大值。

279.完全平方数

同零钱兑换，就是所占的空间要手动计算一下。

139.单词拆分

这个拆分获得的结果是一个排序的问题。 所以先遍历space再遍历单词

关于多重背包

这里的实现是遍历所有的物品。 但是不重新调整数组，而是自己分配物品的index。 先得到一个前缀和，然后根据每次的index获取对应的weight和value