CSES Elevator Rides问题：子集DP解法正确性求证

核心状态定义 #

先明确DP状态的实际意义：

• rides(S)：处理子集S中所有乘客所需的最少电梯趟数
• last(S)：在rides(S)趟的前提下，最后一趟电梯的最小可能重量

维护last(S)是关键——它不是多余信息，而是为后续扩展子集时保留最优的“潜力”：更小的last(S)意味着后续添加新乘客时，更有可能装入最后一趟而无需新增趟数。

正确性证明思路 #

用数学归纳法结合状态转移逻辑拆解：

1. 基础情况

空集∅的状态显然正确：rides(∅)=0（无需电梯），last(∅)=0（最后一趟无重量）。

2. 归纳假设

假设所有大小小于k的子集，rides和last的取值都是正确的（即达到最少趟数，且对应最后一趟重量最小）。

3. 归纳步骤：证明大小为k的子集S的状态正确

对于子集S（大小k），任何一种最优划分（最少趟数的划分）中，最后一趟电梯必然包含至少一位乘客p。将p从S中移除得到子集S\p（大小k-1），根据归纳假设，S\p的状态是正确的。

此时分两种情况讨论：

• 情况1：p可加入S\p的最后一趟（last(S\p) + weight(p) ≤ 电梯限重x）
  此时S的最优趟数等于S\p的趟数（无需新增电梯），最后一趟重量为last(S\p) + weight(p)。这对应将p直接加入S\p最优划分的最后一趟，显然是最优选择。
• 情况2：p无法加入S\p的最后一趟（last(S\p) + weight(p) > x）
  此时必须为p新增一趟电梯，S的最优趟数等于S\p的趟数加1，最后一趟重量为weight(p)。

我们遍历S中的每一位乘客p，计算上述两种情况的可能状态，最终选择：

• 优先选rides最小的状态；
• 若rides相同，选last最小的状态（更小的last对后续扩展更有利）。

为什么遍历所有p不会遗漏最优情况？

任何最优划分的最后一趟必然包含至少一个乘客p，因此去掉p后的子集S\p的最优划分，加上p的处理方式，必然被转移逻辑覆盖。比如，假设最优划分的最后一趟有多个乘客（如p和q），我们可以将p视为最后加入的元素——此时S\p的划分中，q已在最后一趟，last(S\p)包含q的重量，加上p若不超重，转移后的状态和原划分的趟数、最后一趟重量完全一致。

冗余状态的排除 #

为什么只需要维护rides(S)和对应的最小last(S)？
假设有两种划分方式，趟数相同但最后一趟重量为w1和w2（w1 < w2）。对于任何包含S的超集T，w1的划分方式都更优——因为w1能容纳更大的新乘客，避免新增趟数。因此w2的状态是冗余的，无需保留。

示例验证 #

比如：乘客重量[2,2,3]，电梯限重5。

• 子集{2,2}：rides=1，last=4（两乘客同乘一趟）
• 子集{2,3}：rides=1，last=5（两乘客同乘一趟）
• 全集{2,2,3}：遍历每个乘客：
  • 移除第一个2：子集{2,3}的last=5，加2超重，得到rides=2，last=2
  • 移除第二个2：同上，得到rides=2，last=2
  • 移除3：子集{2,2}的last=4，加3超重，得到rides=2，last=3
    最终选择rides=2且last=2的状态，对应最优划分（如{2,2}和{3}），符合预期。

内容的提问来源于stack exchange，提问作者Ivan_Striker