可能出现的简答题

  1. 简述蒙特卡罗算法的使用范围和特点, 以及算法设计的要求
    1. 可以求得问题的一个解，但是该解未必正确
    2. 使用范围：可
  2. 哈夫曼编码树→出现概率→画树
  3. 蒙特卡罗 拉斯维加斯联系与区别
    1. 蒙特卡洛与拉斯维加斯算法都是概率算法
    2. 蒙特卡洛算法可以求得问题的一个解，但该解未必正确；拉斯维加斯算法不会得不到不正确的解，但有时找不到问题的解

代码填空题

不同算法的区别

  1. 动规和贪心的区别

    动规：依赖于已经作出的、未做出的选择和子问题

    贪心：依赖于已经作出的选择，但不依赖于还未做出的选择和子问题，由顶向下

  2. 动规和分治的区别

    动规：各个子问题不是独立，保存已经解决的子问题的答案，而在需要的时候再找出已求得的答案

    分治：各个子问题独立

  3. 动规和备忘录的区别

    动态规划算法：自底向上递归求解

    备忘录方法：自顶向下递归求解，为每个求解过的子问题建立了备忘录以备需要时查看，初始化时，该记录项存入一个特殊值（表示该问题尚未被求解）

贪心大题