首页 > 动态规划 > 动态规划(2)-最优子结构的性质
2014
02-24

动态规划(2)-最优子结构的性质

在上一篇 动态规划(1)-重叠子问题的性质 已经说明只有问题在具有下面两个重要属性时才可以用动态规划:

1)重叠子问题
2)最优子结构

我们在这里讨论的最优子结构性质。

2)最优子结构:如果问题的最优解所包含的子问题的解也是最优的,我们就称该问题具有最优子结构性质(即满足最优化原理)。最优子结构性质为动态规划算法解决问题提供了重要线索。

例如,最短路径问题有以下最优子结构性质:如果一个节点x是到源节点ü的最短路径,同时又是到目的节点V的最短路径,则最短路径从u到v是结合最短路径:u到x和x到v。解决任意两点间的最短路径的算法的Floyd-Warshall算法贝尔曼-福特是动态规划的典型例子。

另一方面最长路径问题不具有最优子结构性质。这里的最长路径是指两个节点之间最长简单路径(路径不循环)。

考虑下算法导论上面的例子:

有两条最长的路径与Q到T:Q – > R – > T和Q – > S-> T。不像最短路径,这些路径最长不具有最优子属性。例如,最长路径q-> r-> t不是由q->r 和 r->t的组合 ,因为最长的路径从q至r为q-> s-> t->r

后续会为大家带来几个常见的动态规划题目。

参考:

http://en.wikipedia.org/wiki/Optimal_substructure

CLRS book (算法导论)

ACM之家原创,链接:http://www.acmerblog.com/optimal-substructure-property-4581.html


  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  2. 嗯 分析得很到位,确实用模板编程能让面试官对你的印象更好。在设置辅助栈的时候可以这样:push时,比较要push的elem和辅助栈的栈顶,elem<=min.top(),则min.push(elem).否则只要push(elem)就好。在pop的时候,比较stack.top()与min.top(),if(stack.top()<=min.top()),则{stack.pop();min.pop();},否则{stack.pop();}.