知识卡片

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

组合计数先枚举币种再金额

理解等级:中级

无限硬币组合计数以dp[0]=1表示空选择,按币种依次处理,每种币在金额递增时累加较小余额的方案数。这样每种组合按固定币种顺序生成,不把选择先后当不同答案。

把金额放外层可能变成计算有序排列,语义不同。面值应正且币种列表互异,重复面值会重复计数,方案数也可能整数溢出;原书倒序注释与实际a++不符,应按正序复用机制解释。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      前 种硬币能够凑出金额 的组合数量 。而 表仍然是尺寸为 的二维矩阵。 当前状态的组合数量等于不选当前硬币与选当前硬币这两种决策的组合数量之和。状态转移方程为: [ , ] = [ −1, ] + [ , − [ − 1

    参考来源

    - 位置:《Hello 算法--Go版本》第14章《动态规划》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/7.html;spine 6,归一字符[27790,27900)) - 结论依据:实际coinChangeII二维/单行及初值,区别最少值、组合和排列。 - 原始内容:前 种硬币能够凑出金额 的组合数量 。而 表仍然是尺寸为 的二维矩阵。 当前状态的组合数量等于不选当前硬币与选当前硬币这两种决策的组合数量之和。状态转移方程为: [ , ] = [ −1, ] + [ , − [ − 1