知识卡片

普通读书笔记卡 · 5654.c.3.g.3

最优子结构要求子解可替换

理解等级:中级

若一个最优完整方案包含的子方案并非对应状态下最优,而且能用更优子方案替换而不破坏后续约束,就能进一步改善完整方案,形成矛盾。这类可组合关系支持从子问题最优值构造原问题最优值。

最小楼梯代价把前1或2阶的更小累计成本加当前cost;本书cost[0]是地面且非负,允许直接到第2阶,不能套用不同平台同名题的起点约定。计数DP则按互斥来源求和,不强行改成最大化。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      原问题的最优解是从子问题的最优解构建得来的 。 [ ] 本题显然具有最优子结构:我们从两个子问题最优解 和 中挑选出较优的那一个,并用 它构建出原问题 的最优解。 那么,上一节的爬楼梯题目有没有最优子结构呢?它的目标是求

    参考来源

    - 位置:《Hello 算法--Go版本》第14章《动态规划》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/7.html;spine 6,归一字符[11860,11970)) - 结论依据:实际最小代价楼梯与初值cost1/cost2支持定义,限定非负和起点。 - 原始内容:原问题的最优解是从子问题的最优解构建得来的 。 [ ] 本题显然具有最优子结构:我们从两个子问题最优解 和 中挑选出较优的那一个,并用 它构建出原问题 的最优解。 那么,上一节的爬楼梯题目有没有最优子结构呢?它的目标是求