动态规划的证明题

动态规划一般用来解决最优解问题，且一般要求这样的问题具有最优子结构和重叠子问题。
证明一个动态规划问题的成立往往在于求证其具有最优子结构：该问题的最优解包含子问题的最优解。
最优子结构的证明步骤：
做出选择，划分子问题，假设该问题最优解成立，而子问题的解不是最优解，反证，利用子问题的最优解推出与该问题最优解矛盾，得证。
下面请看几个实例证明：

1.钢条切割问题

证明：我们不妨选择n英寸长的最优解为i+dp（n-i）其中，i表示n英寸长的有一段分割成i长，另一段长（n-i）可以继续分割，显然子问题是dp（n-i），不妨假设dp（n-i）的分割方案不是最优解，那定有最优解分割t（n-i）>dp(n-i),i+t（n-1）>i+dp（n-i）,显然与i+dp（n-i）为最优解矛盾，所以dp（n-i）也是最优解

2.矩阵链相乘

目的是使得整个式子所需乘法运算标量最小
这里假设Aij为从i到j的最小乘法运算标量，假设其从k处划分为Aik和Ak+1j，则Aij=Aik+Ak+1j+pipk+1pj（pi表示矩阵Ai的行数）。现在Aik、Ak+1j必须也是对应的最小乘法运算标量，不然Aij就不是最小，反证可证。

3.公共子序列

这个问题的最优子结构既是要证明最长公共子序列（LCS）具有最优子结构性。
设两个序列的LCS为Z，则证明Z包含了两个序列前缀的LCS。

即证明如上这个定理即可。
这个问题最优子结构的证明其实同上面两个存在一定的差异，就是没有那么好想，虽然定理6.2的证明也还是利用了反证法，但是将如何证明最长公共子序列（LCS）具有最优子结构性转化成证明定理6.2要花费功夫，希望可以从中受到启发。

4.最优二叉搜索树

最优子结构的证明：假设最优二叉搜索树T为树根的子树为T’，则T’为最优二叉搜索树。
显然，由于T’增加了一个根结点，层次加1，则E（T）=结点概率和+E（T’）,结点概率和是定值，显然要E（T’）是最优二叉搜索树，否则反证法可证。