证明模板

模板一：最优子结构性质（动态规划）

核心方法：剪切-粘贴法 (Cut-and-Paste Argument)

适用场景： 证明“全局最优解的子部分，一定是子问题的最优解”。

口诀： “假如局部的不是最好的，那我换个更好的进去，整体就会变得更好（但这不可能）。”

📝 标准证明步骤：

1. 【设定分解】

   设 是原问题 的一个最优解。

   将 分解为两部分：子问题 的解 和剩余部分 。即 。

2. 【反证假设】 (Cut)

   假设 不是子问题 的最优解。

   这意味着存在另一个解 ，其代价优于 （即 ）。

3. 【构造新解】 (Paste)

   我们将 代入原解，构造一个新的全局解 。

4. 【合法性检查】 (关键得分点！)

   验证 是合法的（例如：没有超过背包容量、路径是连通的等）。

   （注：这一步必须写出来，说明 和 兼容）。

5. 【导出矛盾】

   计算新解的总代价：

   这意味着我们找到了一个比“最优解 ”还要好的解，这与前提矛盾。

6. 【结论】

   假设不成立，因此 必须是子问题 的最优解。

---

模板二：贪心选择性质（贪心法）

核心方法：交换论证法 (Exchange Argument)

适用场景： 证明“我现在的贪心选择，一定包含在某个最优解中”。

口诀： “假设最优解里没选我的贪心项，那我就把那个差的项换成我的贪心项，结果不会变差，说明选我也是对的。”

📝 标准证明步骤：

1. 【假设最优】

   设 是原问题的一个最优解。

   假设 没有包含我们的贪心选择 （例如： 选了 而不是 ）。

2. 【比较差异】

   根据贪心策略的定义（例如最早结束、最轻、最贵）， 在局部指标上优于或等于 。

3. 【执行交换】 (Exchange)

   我们用贪心选择 替换掉 中的元素 ，得到一个新的解 。

4. 【验证优劣与合法性】

   • 合法性： 证明交换后 依然满足约束（例如：时间不冲突、总重没超标）。

   • 优劣性： 由于 比 更优（或相等），所以 不会比 差。

   • 即 （如果是求最小化）。

5. 【结论】

   既然 也是一个最优解，且 包含了贪心选择 。

   说明我们可以安全地做出贪心选择 ，而不会错过最优解。

---

⚡️ 考前 10 秒钟怎么区分？

特征	最优子结构 (DP)	贪心选择性质 (Greedy)
核心动作	Cut & Paste (剪切粘贴)	Exchange (交换)
逻辑本质	拼积木： 坏积木拼不出好房子	换零件： 把旧零件换成新零件，机器照样转
涉及对象	比较 “子解 ” 和 “更好子解 ”	比较 “最优解里的元素 ” 和 “贪心选择 ”
矛盾点	构造出了“更优”的解 (Better)	构造出了“一样好”的解 (Equal/Not Worse)

建议： 考试时，把这两个模板默写在草稿纸上，遇到证明题直接填空！祝你拿满分！