贪婪法解析：局部最优与最优子结构

"贪婪法是算法设计中的一种策略，它基于局部最优选择来逐步构建全局最优解。这种方法适用于具有贪婪选择性质和最优子结构的问题。贪婪选择意味着每次选取局部最优解，以此简化问题到更小的规模。最优子结构是指问题的全局最优解包含了其子问题的最优解。贪婪法与动态规划法的主要区别在于，动态规划考虑的是未来的决策，而贪婪法则只关注当前状态的最优选择。在不能通过贪婪法找到最优解的情况下，动态规划可以提供解决方案。例如，在数塔或多段图问题中，两者的表现有所不同。贪婪法常用于解决背包问题、最小生成树(MST)问题，如Prim和Kruskal算法，以及单源最短路径问题，如Dijkstra算法。在设计贪婪算法时，必须确保每一步选择都是可行的、局部最优的，并且一旦确定就不可更改。然而，贪婪法并不总是能得到全局最优解，因此在应用时需要评估其适用性。例如，找零钱问题中，总是选择最大面额的硬币，可能不总是能得到最少硬币数量的解。"