动态规划最优子结构性质证明

动态规划的最优子结构性质是指问题的最优解可以通过一系列子问题的最优解来构建。证明最优子结构性质通常使用反证法。

假设问题的最优解无法通过子问题的最优解来构建，即存在一个子问题的非最优解。我们可以通过反证法来证明这种情况是不可能的。

假设存在一个子问题的非最优解，记为(y2, y3, ..., yn)，而最优解为(z2, z3, ..., zn)。根据最优子结构性质，我们可以通过子问题的最优解来构建问题的最优解。

现在我们假设(y2, y3, ..., yn)不是子问题的最优解，即存在一个更优的解(y2', y3', ..., yn')。根据这个假设，我们可以构建一个新的解(z2', z3', ..., zn')，其中z2' = y2'，z3' = y3'，..., zn' = yn'。

然而，根据问题的定义，(z2, z3, ..., zn)是问题的最优解，而(z2', z3', ..., zn')是我们通过假设构建的新解。由于(z2', z3', ..., zn')比(z2, z3, ..., zn)更优，这与(z2, z3, ..., zn)是问题的最优解相矛盾。

因此，我们可以得出结论：如果问题具有最优子结构性质，那么子问题的最优解可以构建问题的最优解。