算法面试题：贪心算法与动态规划比较

1. 贪心算法的核心思想是什么？

• 每步选择当前最优解。
• 希望通过局部最优得到全局最优。

2. 动态规划的核心思想是什么？

• 将问题拆分为子问题。
• 保存子问题结果避免重复计算。

3. 贪心与动态规划的主要区别是什么？

• 贪心不一定可回溯。
• 动态规划需要保存状态。
• 贪心适合满足最优子结构和贪心选择性质的问题。

4. 常见贪心题型有哪些？

• 区间调度。
• 背包问题的近似。
• 一些排序与选择题。

5. 常见动态规划题型有哪些？

• 最长子序列。
• 最小路径和。
• 组合计数问题。

6. 面试常问的判断方法有哪些？

• 是否存在局部最优策略。
• 是否需要保存历史状态。
• 是否能通过反例证明贪心失败。