动态规划 vs 贪心算法

在理解动态规划和贪心方法的区别之前，我们应该分别了解动态规划和贪心方法。

什么是贪心方法？

贪心方法是用于解决问题的一种技术。此方法用于解决优化问题。优化问题是需要最大或最小结果的问题。

让我们通过一个例子来理解。

假设我们要从位置 A 移动到位置 B。我们可以通过多种方式从 A 移动到 B，例如步行、自行车、汽车、公共汽车、火车、飞机等。因此，我们有多种解决方案可以实现目标。但是，这个问题中有一个约束条件是，我们必须在 12 小时内到达 B。我们可以通过乘坐飞机或火车来实现此目标。因此，在这种情况下，我们有两个解决方案，即飞机或火车。这些类型的解决方案是可行解决方案。可行解决方案是满足问题中给定的约束条件的解决方案。

假设我们希望以最低的成本覆盖这段距离，那么这被称为最小化问题。最小化问题是需要最低成本的问题。在上述问题中，如果我们乘坐火车，那么它将产生最低成本以提供最佳解决方案。最佳解决方案是提供可行解决方案并产生最低成本的解决方案。这意味着只能有一个最佳解决方案，即不可能有多个解决方案。

这个问题需要最小结果，但有些问题需要最大结果。需要最大或最小结果的问题称为优化问题。

贪心方法表示应该分阶段解决问题。在每个阶段，我们考虑给定问题的输入，如果输入可行，则将其包括在内。通过这种方式，我们包括所有可行的输入以找到最佳解决方案。

贪心方法的算法

在上述贪心算法中，我们传递了两个参数，即 a 和 n，其中“a”是数组，“n”是数组的大小。在 for 循环中，我们从“a”中选择输入值，然后我们检查它是否可行。如果所选输入可行，则将该输入添加到解决方案中。

什么是动态规划？

动态规划是用于解决优化问题的一种技术。以下是动态规划为实现最佳解决方案而遵循的步骤

• 它将复杂的问题分解为更简单的子问题。
• 我们将找到这些子问题的最佳解决方案。
• 存储这些子问题的结果。
• 我们将重用这些子问题的解决方案，因此我们不需要重新计算它们。
• 最后，我们将计算复杂问题的结果。

以上是动态规划用于解决优化问题的五个步骤。动态规划适用于具有以下某些属性的问题

• 重叠子问题：重叠问题是具有共同解决方案的问题。
• 最优子结构：最优子结构是可以通过所有子问题的最佳解决方案的组合获得的子结构。

动态规划和贪心方法的区别