今天这类问题可以说是 再空间和的情况下,最大空间可以放的最少的物品数量。(目前遇到的背包问题可以求解四种问题最大值,最大数量,最小数量和方案数) 322. 零钱兑换 凑成总金额所需的 最少的硬币个数。 无所谓组合还是排序。 然后转移方程是min ,注意初始化的时候要取极大值。 279.完全平方数 同零钱兑换,就是所占的空间要手动计算一下。139.单词拆分 这个拆分获得的结果是一个排序的问题。 所以先遍历space再遍历单词 关于多重背包这里的实现是遍历所有的物品。 但是不重新调整数组,而是自己分配物品的index。 先得到一个前缀和,然后根据每次的index获取对应的weight和va...