#动态规划

算法设计与分析：分治、动态规划与贪心算法的异同与选择

分治、动态规划和贪心算法是计算机科学中解决复杂问题的三种核心策略。它们都将原问题分解为子问题，但在处理方式上有本质区别：分治法适用于子问题独立且合并简单的场景（如归并排序）；动态规划通过存储重叠子问题的解来保证全局最优（如0-1背包）；贪心算法每步选择局部最优，仅当问题具有贪心性质时才能保证全局最优（如活动选择）。选择算法需考虑子问题的独立性、重叠性以及对最优解的要求。