我看到人们倾向于 DP 方法而不是贪婪方法，因为它可以解决优化问题。大家觉得哪一个更可取呢？我需要收集论据以支持与我的伙伴争论的更好技术。哈哈。好的，DP用于解决具有最优子结构和最优性原理的问题。但是DP比贪婪的方法更好吗？
问问题
2054 次
2 回答
4
不知道您要解决什么问题，您的问题毫无意义。
动态规划是一种工具。它对于解决某一类问题很有用。
贪心算法是另一种工具。它们在其他情况下很有用。
这就像问“哪个更好 - 锤子或锯子”？
The answer will be very different depending on what you are trying to do.
于 2012-07-10T06:20:37.003 回答
2
让我们以硬币变化为例。如果您采用贪婪方法，大多数时候您可能无法得到正确的结果，但如果您采用 DP 方法，您将始终得到正确的结果。事实上，解决问题的唯一方法就是使用DP。
要回答您的问题，请忘记最优性，但使用 Greedy 您可能无法首先获得针对某些问题的正确解决方案。
于 2012-07-10T06:20:20.623 回答