解决方案使用动态编程或贪婪的方法的问题？

本文介绍了解决方案使用动态编程或贪婪的方法的问题？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

应该问题有什么样的属性，这样我可以决定使用动态规划和贪婪的方法，该方法？

What properties should the problem have so that I can decide which method to use dynamic programming or greedy method?

推荐答案

动态规划问题具有最优子结构。这意味着，解决问题的方法可以是pssed作为解决方案的功能的子是严格较小的前$ P $

Dynamic programming problems exhibit optimal substructure. This means that the solution to the problem can be expressed as a function of solutions to subproblems that are strictly smaller.

的这样的问题的一个例子是矩阵链乘法的

One example of such a problem is matrix chain multiplication.

贪婪算法可以用来仅当局部最优选择导致完全最优解。这也很难马上看到，但一般比较容易实现，因为你只有一件事要考虑（贪婪的选择）而不是多个（在解决所有小的子问题）。

Greedy algorithms can be used only when a locally optimal choice leads to a totally optimal solution. This can be harder to see right away, but generally easier to implement because you only have one thing to consider (the greedy choice) instead of multiple (the solutions to all smaller subproblems).

一个著名的贪心算法是 Kruskal算法查找最小生成树。

One famous greedy algorithm is Kruskal's algorithm for finding a minimum spanning tree.