知识卡片

普通读书笔记卡 · 1292.g.1.f · 生成模型:未记录

关联子问题要防止重复求解

理解等级:中级

动态规划针对分解后有关联、可能重复出现的子问题组织求解,避免把同一工作无意义地多做多次。它与分治的关键对照在子问题关系,不能只看到“大问题拆小问题”就断言应采用哪一种方法。

这一节没有展开状态定义、递推式、求解顺序或具体动态规划实现,明确说后面的示例未使用它。因而这里保留的是方法区别与动机,不补成可直接套用的实现模板。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      有些子问题会重复计算多次。尽管动态规划法是一种重要的思想且很多算法都利用了这种思想,但本书介绍的算法中都没有使用到它。 贪心法 贪心法在求解问题时总能够做出在当前的最佳选择。换句话说,不是从整体最优上考虑,而仅仅是在某种意义上的局部最优解。遗憾的是,当前的最优解长远来看却未必是最优的。因此,贪心法并

    参考来源

    - 位置:《算法精解:C语言描述》第1章《算法设计的一般方法》(spine1180;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1148.html;u016-ch01-007)。 - 结论依据:16动态规划段把子问题关联与重复计算作为区别,并明确本书后续没有此类实现;卡片保留动机而不补状态表。 - 原始内容:有些子问题会重复计算多次。尽管动态规划法是一种重要的思想且很多算法都利用了这种思想,但本书介绍的算法中都没有使用到它。 贪心法 贪心法在求解问题时总能够做出在当前的最佳选择。换句话说,不是从整体最优上考虑,而仅仅是在某种意义上的局部最优解。遗憾的是,当前的最优解长远来看却未必是最优的。因此,贪心法并