一类常见问题，对序列 \(a_1, a_2, \cdots, a_n\) 。若任意 \(k\) 都满足 \(a_{k}\) 的匹配集是 \(a_{k + 1}\) 匹配集。
- 不难证明，按从 \(a_1\) 到 \(a_n\) 的顺序，贪心地尽可能匹配，比能匹配却不匹配更优。
- 进一步可以证明，从 \(a_1\) 到 \(a_n\) 的顺序，任选匹配都最优。
如果不存在这个性质，如果能构造 \(k\) 个满足条件的非空匹配集，也等于拥有这个性质。
这个问题的经典例子是：
\(a_1, a_2, \cdots, a_n\) 满足 \(\forall 1 \leq i < j \leq n\) ，\(a_i\) 和 \(a_j\) 都匹配一段后缀且 \(a_i\) 匹配的后缀包含于 \(a_j\) 匹配的后缀。
比如限制 \(x + y \leq W\) 的匹配数。
证明：
设值满足 \(a_1 \leq a_2 \leq \cdots \leq a_n\) 。对于 \(a_1\) 有最大的 \(k\) 满足 \(x \in \mathbb{L} = \{a_k, a_{k + 1}, \cdots, a_{n}\}\) 有 \(x + a_1 \leq W\) ，任选 \(a_x\) 满足 \(x > 1\) ，有最大的 \(l\) 满足 \(l \leq k, y \in \mathbb{S} = \{a_l, a_{l + 1}, \cdots, a_{n} \}\) 有 \(y + a_x \leq W\) 。
若 \(|\mathbb{L}| = 0\) ，则 \(a_1\) 只能不匹配，并且不影响 \(a_x\) 的匹配。
若 \(|\mathbb{L}| = 1\) ，不难证明 \(a_1\) 与唯一可匹配的 \(a_n\) 匹配最优，进而 \(a_x\) 在 \(\mathbb{L} \backslash \mathbb{H}\) 中匹配最优。于是 \(a_1\) 的匹配不影响 \(a_x\) 的匹配。
若 \(|\mathbb{L}| > 1\) ，\(a_1\) 在 \(\mathbb{L}\) 中选择一个匹配，不影响 \(a_x\) 从至少还存在一个元素的 \(\mathbb{L}\) 中匹配，也不影响 \(a_x\) 从 \(\mathbb{L} \backslash \mathbb{H}\) 中匹配。那么 \(a_1\) 与 \(\mathbb{L}\) 中任意一元素匹配都属于不影响子问题的匹配。
在子问题中继续递归地归纳，可以证明贪心地任意匹配是一种最优匹配。
\(\square\)
这个例子存在等价表述：“从大到小贪心地任意匹配”显然和“从大到小贪心地和最小值匹配”是充要的。