所有贪婪能解决的问题也能用动态规划解决吗
如果一个问题的最优解可以通过贪婪得到，那么它也可以通过动态规划得到吗？既然贪婪和dp都在处理子问题的最优解，那么可以说dp可以解决贪婪可以解决的所有问题吗？
共有1个答案
比较贪心和DP就像把橘子比作苹果。但是一个简单的想法是
贪婪的方法：选择你现在认为最佳的方法，假设它从长远来看是最佳的
例如，当你开车时，看到一条路上堵车，你可能会选择另一条看起来空旷的道路。这可能有效，但另一条道路拐角处可能会出现更严重的交通拥堵。
另一方面，动态编程使用内存来存储您之前所做的计算/结果，以便在下次需要时节省时间。再次使用上述问题，DP解决方案将是计算每条道路上的交通量，然后选择提供最佳（最佳）时间的道路。
从这个意义上讲，DP更像是一种分而治之的方法，但有记忆。您不会反复计算子问题的结果。
为了回答你的问题
可以肯定地说dp可以解决所有贪婪可以解决的问题吗
我认为可以肯定地说dp可以解决分而治之可以解决的所有问题（虽然可能需要更多的内存）
在我能想到的所有例子中，DP可以为可以通过贪婪最佳解决的问题提供最佳解决方案（尽管DP可能需要指数时间，而且几乎在每种情况下DP都会占用更多内存）。
-
以人民币的硬币为例，假设硬币数量足够多。要求将一定数额的钱兑换成硬币。要求兑换硬币数量最少。 思路说明： 这是用贪婪算法的典型应用。在本例中用python来实现，主要思想是将货币金额除以某硬币单位，然后去整数，即为该硬币的个数；余数则做为向下循环计算的货币金额。 这个算法的问题在于，得出来的结果不一定是最有结果。比如，硬币单位是[1,4,6],如果将8兑换成硬币，按照硬币数量最少原则，应该兑换成为
-
硬币行问题：有一行n枚硬币，其值为一些正整数C0，C2，Cn-1，不一定不同。目标是提取最大金额的货币，但受限制，不能提取初始行中相邻的两个硬币。 在下面的代码中，n是我的数组C的大小（或硬币的数量），这段代码返回了值[10, 2, 4, 6, 3, 9, 5]的正确结果（正确的结果是25）。但是当我为值[3,12,10]或[3, 12, 10, 2]运行相同的代码时，我得到了错误的结果。（该组值
-
本文向大家介绍贪婪方法与动态规划的区别，包括了贪婪方法与动态规划的区别的使用技巧和注意事项，需要的朋友参考一下 在这篇文章中，我们将了解贪婪算法和动态编程方法之间的区别。 贪心算法 它是一种算法范式，它逐步地建立在解决方案上。选择下一步，以便它给出最明显和最直接的好处。 涉及选择局部最优值的问题将有助于选择全局最优值/问题的解决方案。这样就解决了与贪婪算法相关的问题。 不能确定贪婪算法会导致最佳解
-
大部分软件都可以通过付出相对较小的努力，让他们比刚发布时快上10到100倍。在市场的压力下，选择一个简单而快速的解决问题的方法是比选择其它方法更为明智而有效率的选择。然而，性能是可用性的一部分，而且通常它也需要被更仔细地考虑。 提高一个非常复杂的系统的性能的关键是，充分分析它，来发现其“瓶颈”，或者其资源耗费的地方。优化一个只占用1%执行时间的函数是没有多大意义的。一个简要的原则是，你在做任何事情
-
本文向大家介绍PHP动态规划解决0-1背包问题实例分析，包括了PHP动态规划解决0-1背包问题实例分析的使用技巧和注意事项，需要的朋友参考一下 本文实例分析了PHP动态规划解决0-1背包问题。分享给大家供大家参考。具体分析如下： 背包问题描述：一个承受最大重量为W的背包，现在有n个物品，每个物品重量为t, 每个物品的价值为v。 要使得这个背包重量最大(但不能超过W),同时又需要背包的价值最大。 思
-
斐波那契数列 1. 爬楼梯 2. 强盗抢劫 3. 强盗在环形街区抢劫 4. 信件错排 5. 母牛生产 矩阵路径 1. 矩阵的最小路径和 2. 矩阵的总路径数 数组区间 1. 数组区间和 2. 数组中等差递增子区间的个数 分割整数 1. 分割整数的最大乘积 2. 按平方数来分割整数 3. 分割整数构成字母字符串 最长递增子序列 1. 最长递增子序列 2. 一组整数对能够构成的最长链 3. 最长摆动子