知识卡片
动态规划先解子题再选择
动态规划通常先求候选子问题的最优值,再比较哪个选择组成全局解;
贪心则先作眼前最好的选择,再求余下子问题。
两者都可能有最优子结构,但仅凭此性质不能推断贪心正确。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 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.