贪心算法与动态规划的区别 @R 动态规划算法 Φ每一步的最优解是由上一步的局部最优解进行选择得到的 因此需要保存（之前求解的)所有子问题的最优解备查 3 贪心算法 贪心策略：下一步的最优解是由上一步的最优解推导得到的 当前最优解包含上一步的最优解，之前的最优解则不作保留 因此在贪心算法中作出的每步决策都无法改变（不能回退） 3 二者关系 贪心算法本质上是一种（更快的） 动态规划算法 贪心法正确的条件：每一步的最优解一定包含上一步的最优解 如果可以证明：在递归求解的每一步，按贪心选择策略选出的 局部最优解，最终可导致全局最优解，则二者是等价的贪心算法与动态规划的区别  动态规划算法  每一步的最优解是由上一步的局部最优解进行选择得到的  因此需要保存（之前求解的）所有子问题的最优解备查  贪心算法  贪心策略：下一步的最优解是由上一步的最优解推导得到的  当前最优解包含上一步的最优解，之前的最优解则不作保留  因此在贪心算法中作出的每步决策都无法改变（不能回退）  二者关系  贪心算法本质上是一种（更快的）动态规划算法  贪心法正确的条件：每一步的最优解一定包含上一步的最优解  如果可以证明：在递归求解的每一步，按贪心选择策略选出的 局部最优解，最终可导致全局最优解，则二者是等价的