知识卡片
恰好凑额要显式标不可达
最少硬币问题要求恰好达到金额,不像背包只要求不超过容量。金额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 章 动态规