知识卡片

普通读书笔记卡 · 3623.f

重叠子问题是重复状态

理解等级:中级

动态规划的第二条件是不同递归分支反复遇到同一个子问题,而不同状态总数通常远小于递归调用数,常为多项式。缓存同一状态可消除重复计算;分治若每步产生全新子问题,记忆化通常无从节省。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第4版)》第 14 章 14.3–14.4 节(`OEBPS/chapter014.xhtml`,文本字符 [55000, 65000))。 - 结论依据:14.3 节将重叠定义为递归反复遇到相同状态,且不同状态总数通常较少;表中一次求解、后续查表与分治产生新子题相区别。 - 原始内容:When a recursive algorithm revisits the same problem repeatedly, we say that the optimization problem has overlapping subproblems .