算法问题求解策略：动态规划、分治法、贪心法与回溯法

算法问题求解策略：动态规划、分治法、贪心法与回溯法

动态规划

• 将问题分解为重叠子问题
• 利用子问题的解构建原问题的解
• 适用于具有最优子结构性质的问题

分治法

• 将问题分解为独立子问题
• 递归求解子问题
• 合并子问题的解得到原问题的解
• 适用于可以分解为相互独立且相同类型子问题的问题

贪心法

• 每一步都做出局部最优选择
• 期望通过局部最优选择达到全局最优
• 适用于具有贪心选择性质的问题

回溯法

• 逐步构建问题的解
• 当发现当前路径无法得到有效解时，回退到上一步
• 尝试其他路径
• 适用于需要探索所有可能解空间的问题