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

  • 关注下方微信公众号，在线模考后查看

热门试题