请叙述动态规划算法与贪心算法的异同。
正确答案:
共同点：
都需要最优子结构性质，
都用来求有优化问题。
不同点：
动态规划：每一步作一个选择—依赖于子问题的解。
贪心方法：每一步作一个选择—不依赖于子问题的解。
动态规划方法的条件：子问题的重叠性质。
可用贪心方法的条件：最优子结构性质；贪心选择性质。
动态规划：自底向上求解；
贪心方法：自顶向下求解。
可用贪心法时，动态规划方法可能不适用；
可用动态规划方法时，贪心法可能不适用。
都需要最优子结构性质，
都用来求有优化问题。
不同点：
动态规划：每一步作一个选择—依赖于子问题的解。
贪心方法：每一步作一个选择—不依赖于子问题的解。
动态规划方法的条件：子问题的重叠性质。
可用贪心方法的条件：最优子结构性质；贪心选择性质。
动态规划：自底向上求解；
贪心方法：自顶向下求解。
可用贪心法时，动态规划方法可能不适用；
可用动态规划方法时，贪心法可能不适用。
答案解析:有
微信扫一扫手机做题