返回信息流迪杰斯特拉算法是属于贪心还是动态规划呢？《算法导论》里明确说了是贪心的典型应用，而维基百科上又说是属于动态规划范畴。查了知乎上关于这个问题的答案，也是分为两拨不同的观点。
我看了一些博客，说贪心算法可以依赖于以往做出的选择，但不依赖于子问题的求解，也不依赖于将来的选择，是一系列局部最优解。这样说迪杰斯特拉是属于贪心的，而且它也没有动态规划里所谓的状态转移。
可我觉得迪杰斯特拉是整体最优解，并不是当前最优解啊(可能是我理解错误)，当前路径权值小于上一步权值时，是要更改节点路径的。求大神指点。
而且不太懂什么是自底向上的解决方法。。。。
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #91550同步于 2016/10/26
该镜像源已超过 30 天没有更新，可能在源站已被删除。
ACM_ICPC机器人发帖
请教大神贪心与动态规划
liqiu
2016/10/26镜像同步8 回复
订阅后，新回复会通过你的通知中心匿名送达。
8 条回复
对于找全局最优解问题，动态规划可以保证可以找到全局最优解。贪心算法不能保证一定能找到全局最优解。
动态规划在你“规划”的过程中，可以使用贪心的思想。只要你能保证贪心的结果是一定正确的。那么就可以这么规划。
所以说，既是贪心，也是DP。
寻找到某点的最短路径，只需要找到所有相邻点到这个点的最短路径，然后加上到相邻点长度。这就是动态规划思想。贪心就是每次都找到目标最近的相邻点。
发自「贵邮」
每一个贪心算法的背后都有一个比较笨拙的DP解法
【 在 wk1948 的大作中提到: 】
: 寻找到某点的最短路径，只需要找到所有相邻点到这个点的最短路径，然后加上到相邻点长度。这就是动态规划思想。贪心就是每次都找到目标最近的相邻点。
发自「贵邮」
发自「贵邮」
f(i)=f(i-1)+f(i-2)是自顶向下，知道了f(1)=f(2)=1依次求f(3),f(4),f(5)是自底向上。
自底向上就是从边界条件出发，根据公式做递推。
嗯嗯，我又看了几篇博客，问了算法老师，老师也是这么说的，给你点赞[ema4]
【 在 Sluggard 的大作中提到: 】
: 对于找全局最优解问题，动态规划可以保证可以找到全局最优解。贪心算法不能保证一定能找到全局最优解。
: 动态规划在你“规划”的过程中，可以使用贪心的思想。只要你能保证贪心的结果是一定正确的。那么就可以这么规划。
: 所以说，既是贪心，也是DP。
是的，算法老师也这么说，说两部分有重叠的部分，谢谢你~
【 在 leezheng 的大作中提到: 】
: 这两个里面本来就没有非常明显的界限，可以说是在每一步DP过程中用到了贪心思想
原来是这样，谢谢你
【 在 kit 的大作中提到: 】
: f(i)=f(i-1)+f(i-2)是自顶向下，知道了f(1)=f(2)=1依次求f(3),f(4),f(5)是自底向上。
: 自底向上就是从边界条件出发，根据公式做递推。