当我遇到最优子结构的问题并且没有子问题共享子问题时,我可以使用分而治之的算法来解决它吗？
但是当子问题共享子问题(重叠的子问题)时,我可以使用动态编程来解决问题吗？
它是否正确？
贪婪算法与动态编程有何相似之处？
当我遇到最优子结构的问题并且没有子问题共享子问题时,我可以使用分而治之的算法来解决它吗？
是的,只要您能为每种子问题找到最佳算法.
但是当子问题共享子问题(重叠的子问题)时,我可以使用动态编程来解决问题吗？
它是否正确？
是.动态编程基本上是Divide&Conquer算法系列的一个特例,其中所有子问题都是相同的.
贪婪算法与动态编程有何相似之处？
他们是不同的.
动态编程为您提供最佳解决方案.
贪婪算法通常在很短的时间内提供良好/公平的解决方案,但不能保证达到最佳状态.
比方说,它是相似的,因为它通常将解决方案结构分为几个阶段,在这些阶段中,它采取局部最优的选择.但如果阶段不是原始问题的最优子结构,那么通常它不会导致最佳解决方案.
编辑:
正如@rrenaud所指出的,有一些贪婪的算法已被证明是最优的(例如Dijkstra,Kruskal,Prim等).
因此,更正确的是,贪婪和动态编程之间的主要区别在于前者在解决方案的空间上并不详尽,而后者则是.
事实上,贪婪算法在这个空间上是短视的,并且在解决方案构建期间做出的每个选择都不会被重新考虑.