证明最优子结构的其他方法：可否通过子问题最优反推原问题最优？

核心结论 #

不能仅通过证明你提到的逆命题完成最优子结构验证。CLRS教材给出的「原问题最优解可推导子问题解最优」的逻辑才是最优子结构的核心判定标准，逆命题仅可作为动态规划转移正确性的补充验证条件，无法单独用来判定最优子结构成立。

两个命题的本质差异 #

我们可以先明确两个命题的逻辑定位：

• CLRS常规证明的是最优子结构的核心要求：如果S是原问题的最优解，那么从S拆分出的所有子问题对应解s₁、s₂……sₙ，一定是对应子问题的最优解。
  这个命题的价值是保证原问题的最优解一定能被拆分为子问题最优解的组合，不会出现某个全局最优解拆分后子解不是子问题最优的情况，也就是说动态规划只需要枚举子问题最优解的组合，就一定能找到全局最优，不会漏掉可行的最优解。
• 你提到的逆命题：如果s₁、s₂……sₙ是各子问题的最优解，那么用组合函数f拼接得到的S一定是原问题的最优解。
  这个命题的天然缺陷是没有考虑子问题最优解的兼容性：不同子问题的最优解可能互相冲突，拼接后甚至不满足原问题的合法性约束，更谈不上是最优解。

反例验证 #

我们用图论中经典的最长简单路径问题举例，就能很直观看到逆命题的问题：

给定4个节点的无向完全图，所有边权为1，原问题为求节点1到节点4的最长简单路径（要求路径中不能出现重复节点）。
子问题1：求1到2的最长简单路径，最优解为1→3→4→2，长度为3。
子问题2：求2到4的最长简单路径，最优解为2→1→3→4，长度为3。
按照逆命题的逻辑拼接两个子问题的最优解，得到的路径存在重复节点1、3、4，连合法的简单路径都不是，完全不符合原问题的要求。
这个例子已经能说明，仅证明逆命题成立没有实际意义，你甚至没法保证子问题最优解的组合是原问题的合法解。

逆命题的实际作用 #

逆命题也不是完全没有价值：当你已经通过CLRS的常规方法证明了最优子结构成立之后，再补充证明逆命题成立，就可以保证动态规划转移方程的正确性——即只要取子问题最优解按照转移函数拼接，就能得到原问题的最优解。但这个步骤只是补充验证，绝对不能替代核心的最优子结构证明。 #

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