如何证明一个动态规划策略是否适用于一个算法？

Question

如何证明针对问题的动态规划(dp)策略是否有效？对于贪婪算法，我们可以通过证明子问题具有拟阵性质来证明。对于dp算法，有这样的方法吗？

Answer 1

通常，可以通过显示您的解具有最优子结构属性来证明动态规划解。

基本上，您将实际问题表述为由较小的子问题组成的问题，然后将这些解决方案组合起来得到最终的答案。在组合中，如果问题的大小增加，那么对于较小的子问题的解决方案仍然必须是组合实际工作的最佳方案。

例如，如果在图中你试图找到A和C之间的最短路径，而你已经知道这条路通过中间点B，并且你已经知道从A到B的最短路径，那么你只需要找到一条最短的从B到C的路径，你就不用担心找到一条从A到C的新路径，这就是最优子结构属性的意思。对于动态编程正确性的证明，证明这个属性就足以证明您的方法是正确的。

它们通过显示拟阵结构来证明贪婪算法是正确的，但它并不总是有效的。一些贪心算法不会显示Matroid结构，但它们是正确的贪婪算法。例如，Huffman编码方案是一种贪婪的方法，但它不具有拟阵结构。

要证明贪婪算法，通常需要证明您的解决方案具有-1)最优子结构特性，如DP和2)贪婪方法所作的选择并不是次最优(基本上表明它是最优的，或者是当时可以作出的最优选择之一)。