如何形式化证明两个DP问题等价？以砸石与子集划分问题为例

嘿，这个问题问得特别到位——DP问题的等价性证明确实是容易卡壳的点，尤其是当两个问题看起来场景完全不搭的时候。咱们先从通用方法聊起，再聚焦到你提到的这两个具体问题上。

我常用的思路主要有这几个，你可以根据问题场景选：

• 双向归约法：这是最核心的方法。你需要证明两个问题能互相转化——也就是说，问题A的任意一个实例，都能转成问题B的实例，而且A的最优解对应B的最优解；反过来，问题B的实例也能转成A的实例，解也能对应回去。这种方法比归纳法更灵活，尤其是当问题的操作顺序不固定、难找到归纳结构的时候。
• 状态与转移的对应：如果两个问题的DP状态能一一对应，而且状态转移的逻辑完全一致，那它们本质上就是同一个问题的不同包装。比如，两个问题的最优子结构、重叠子问题的模式完全匹配，只是换了个场景描述而已。
• 归纳法（按需使用）：如果问题有明显的规模递增结构（比如数组长度从n到n+1），可以试试归纳。但得先找对归纳假设——比如假设数组长度为k时两个问题等价，再证明k+1时也成立。不过有些问题（比如砸石头的操作顺序太灵活）会让归纳结构很难设计，这时候归约法就更顺手。

咱们直接抓两个问题的数学本质，用双向归约来证，比归纳法清晰多了：

首先，先明确两个问题的核心目标：

• 砸石问题：每次操作把两个石头a、b换成|a-b|，最终剩下的石头，本质上是所有石头大小通过一系列加减（带绝对值）运算得到的结果。根据数论结论，最终能得到的最小非负结果，一定是所有数的线性组合中，能被它们的最大公约数整除的最小数。
• 最小差子集划分：设数组总和为S，我们要找一个子集，其和为T，使得|S - 2T|最小——也就是让两个子集的和的差值尽可能小。

1. 砸石问题的解 → 子集划分的解 #

假设砸石问题最终剩下的最小石头大小为m，那么m必然可以表示为|sum(X) - sum(Y)|，其中X和Y是原石头集合的一个划分（X∪Y是原集合，X∩Y为空）。因为每次砸石头的操作，本质上就是把一些石头的和减去另一些石头的和（取绝对值）——比如，把所有被“减去”的石头归为Y，被“加上”的归为X，最终的剩余值就是两组和的差的绝对值。而砸石问题要找最小的m，正好对应子集划分问题中最小的|sum(X)-sum(Y)|，也就是最小的|S-2sum(X)|（因为sum(Y)=S-sum(X)）。

2. 子集划分的解 → 砸石问题的解 #

假设我们在子集划分问题中找到了最优解，即最小的|S-2T|（T是某个子集的和），那么我们可以通过合理的砸石头操作，得到这个差值作为最终剩余的石头：
比如，先把属于子集T的石头两两相撞，最终可以合并成一个大小为T的“超级石头”（因为多次相减的结果，其实等价于这组石头的和的绝对值——当然这里子集里的石头都是正数，所以就是T）；同理，另一组石头合并成S-T的“超级石头”。最后让这两个超级石头相撞，得到的就是|(S-T)-T|=|S-2T|，也就是砸石问题的最小剩余值。

为什么归纳法在这里不好用？ #

主要是砸石头的操作顺序太灵活了——每次操作后，石头的集合形态可能千差万别，很难找到一个统一的归纳结构（比如按石头数量n归纳时，n-1的状态可能有很多种，没法统一对应到子集划分的状态）。而双向归约直接跳过了操作顺序的干扰，抓住了两个问题的核心数学目标，证明起来更直接。

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