知识卡片

普通读书笔记卡 · 3623.e

动态规划先解子题再选择

理解等级:高级

动态规划通常先求候选子问题的最优值,再比较哪个选择组成全局解;

贪心则先作眼前最好的选择,再求余下子问题。

两者都可能有最优子结构,但仅凭此性质不能推断贪心正确。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第14章 动态规划 · 查看原书依据

      One major difference between greedy algorithms and dynamic programming is that instead of first finding optimal solutions to subproblems and then making an informed choice, greedy algorithms first make a “greedy” choice—the choice that looks best at the time—and then solve a resulting subproblem, without bothering to solve all possible related smaller subproblems.

    参考来源

    - 位置:《算法导论(第4版)》第 14 章 14.3–14.4 节(`OEBPS/chapter014.xhtml`,文本字符 [50000, 55000))。 - 结论依据:14.3 节明确动态规划先求相关子题最优值再选,贪心先取当前看来最好的选择再解余题;最优子结构本身不保证贪心成立。 - 原始内容:One major difference between greedy algorithms and dynamic programming is that instead of first finding optimal solutions to subproblems and then making an informed choice, greedy algorithms first make a “greedy” choice—the choice that looks best at the time—and then solve a resulting subproblem, without bothering to solve all possible related smaller subproblems.