动态规划与贪心算法的异同点

贪心算法与动态规划的区别 

贪心算法与动态规划的主要区别如下：

1. 基本思想：贪心算法每次只考虑当前状态下的最优选择，而不会考虑之后的影响。动态规划则需要计算和保存大量的中间结果，通过不断的决策和回溯来找到最优解。

2. 时间和空间复杂度：贪心算法通常只需要一次遍历，无需计算和保存大量中间结果，因此在时间和空间上的复杂度较低。动态规划算法适用于有重叠子问题的情况，通常需要计算和保存大量的中间结果，因此在时间和空间上的复杂度较高。

3. 求解方式：动态规划算法中，每步所做的选择往往依赖于相关子问题的解，因而只有在解出相关子问题时才能做出选择。而贪心算法，仅在当前状态下做出最好选择，即局部最优选择，然后再去解做出这个选择后产生的相应的子问题。动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常自顶向下的方式进行。

4. 适用情况：贪心算法适用于无重叠子问题的情况，而动态规划算法适用于有重叠子问题的情况。

需要注意的是，贪心算法和动态规划算法并不是互斥的，有些问题可以同时使用两种算法进行求解。