反证法证明

一句话理解

反证法：假设贪心错，推出矛盾。

为什么要学

另一种证明。

讲解

假设存在更好解，它必须在某处违反贪心选择，再推出它不会更好。

例子

若某解选了更晚结束的活动，总个数不会超过按结束早的选法。

常见错误

• 反证没有用到题目条件。
• 矛盾推到一半停下。