day38 | 动规

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

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

322. 零钱兑换

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

279.完全平方数

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

139.单词拆分

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

关于多重背包

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

全部评论

相关推荐

点赞 收藏 评论
分享
牛客网
牛客企业服务