07-分治算法

type
status
date
slug
summary
tags
category
icon
password
把一个复杂问题分成两个或多个子问题，递归解决子问题，然后再将子问题的解合并，得到原问题的解。
  • 分解（Divide）：将问题划分为若干个子问题；
  • 解决（Conquer）：递归求解每个子问题；
  • 合并（Combine）：将子问题的结果合并得到原问题的解。

二分查找（基础的分治）

归并排序（Merge Sort）

快速排序（Quick Sort）

求数组中最大值（分治）

最大子数组和（LeetCode 53）分治写法

 

分治 vs 动态规划

维度
分治算法
动态规划
子问题是否重叠
否
是
是否自底向上
否（自顶向下）
是（也有记忆化）
是否记忆缓存
否
是
是否合并子解
是
是
 
上一篇
06-贪心算法
下一篇
08-回溯算法
Loading...