问贪婪能解决的所有问题都能用动态规划解决吗？

EN

比较贪婪和DP就像比较橘子和苹果一样。但一个简单的想法是

贪婪方法：选择您认为最优的任何东西，假设从长远来看是最优的。

例如，当你在一条道路上看到交通堵塞时，你可能会走另一条看上去空无一人的道路。这可能会奏效，但在拐角处，备用道路可能会出现更严重的交通堵塞。

另一方面，Dynamic Programming使用内存存储以前为节省下一次需要它们时的时间所做的计算/结果。再次使用上述问题，DP求解的方法是计算每条道路的流量，然后选择给出最佳(最优)时间的道路。

从这个意义上讲，DP更像是一种除法和征服方法，而则是带内存的。您不会一次又一次地计算子问题的结果。

回答你的问题

可以肯定地说，dp可以解决所有贪婪可以解决的问题吗？

我认为可以肯定地说，dp可以解决所有问题，分而治之可以解决(虽然可能占用更多内存)。

在我能想到的所有例子中，，DP可以给出最优解，可以用贪婪来最优地解决问题(DP可以用指数时间，，几乎在每种情况下，DP都需要更多的内存)。