知识卡片

普通读书笔记卡 · 5654.c.3.b.3.a.1.a.2.a

恰好凑额要显式标不可达

理解等级:中级

最少硬币问题要求恰好达到金额,不像背包只要求不超过容量。金额0需要0枚,其他没有来源的金额应标不可达;选择一枚后,把剩余金额的最少数量加1。

正面值保证过程进展,非负金额和可用内存也是前提。用amt+1作哨兵依赖结果上界且它本身不能溢出;不可达与合法0不能混用。原书压缩版注释说倒序,实际代码正序,机制应按可重复硬币理解。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      本题要求最小值,因此需将运算符max 更改为min 。 +1 ‧ 优化主体是硬币数量而非商品价值,因此在选中硬币时执行 即可。 [ , ] = min −1, ], [ , − [ −1]] + 1) 第14 章 动态规

    参考来源

    - 位置:《Hello 算法--Go版本》第14章《动态规划》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/7.html;spine 6,归一字符[25905,26015)) - 结论依据:实际coinChange状态/哨兵/初值/转移和压缩代码,保持精确目标与数值约束。 - 原始内容:本题要求最小值,因此需将运算符max 更改为min 。 +1 ‧ 优化主体是硬币数量而非商品价值,因此在选中硬币时执行 即可。 [ , ] = min −1, ], [ , − [ −1]] + 1) 第14 章 动态规