分治，动态规划与贪心算法

子问题非重复求解，用分治；
子问题重复求解，组合得到原问题解，用动态规划；
贪心算法可求解的，动态规划总可求解；贪心适用于原问题做出一个最优选择后，只剩下一个子问题需要求解的场景；组合最优选择和子问题的解，可得出原问题的解；贪心算法只要可解，预期实现比动态规划更简单。

1 分治算法(Divide and Conquer)

1.1 方法

典型三步：

分解(Divide)：把问题划分为子问题；子问题形式与原问题一致，但规模更小；
解决(Conquer)：递归求解子问题；子问题规模足够小时，停止递归，直接求解；
合并(Combine)：组合子问题的解，得到原问题的解。

\begin{equation} T(n) = \left\{ \begin{aligned} 1 \qquad \qquad if n = 1\\ T(\frac{n}{2}) \qquad if n > 1 \end{aligned} \right\} \end{equation}

1.2 示例

From 算法导论，最大子数组问题。

给定数组:
13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -15, -22, 15, -4, 7
找出最大子数组，这个子数组之后，是所有子数组里最大的。

暴力破解法可以在O(n^2)时间内完成，尝试用分治算法求解。

考虑子数组[i..j]中间位置mid，[i..j]可以划分为两个子数组[i..mid], [mid+1, j]，只要找到最大子数组[i..mid]和[mid+1 .. j]，合并就能得到最大的[i..j]。

书中给出的伪代码如下：

FIND-MAX-CROSSING-SUBARRAY(A, low, mid, high)
1 left-sum = -∞
2 sum = 0
3 for i = mid downto low
4     sum = sum + A[i]
5     if sum > left-sum
6         left-sum = sum
7         max-left = i
8 right-sum = -∞
9 sum = 0
10 for j = mid + 1 to high
11    sum = sum + A[j]
12    if sum > right-sum
13        right-sum = sum
14        max-right = j
15 return (max-left, max-right, left-sum + right-sum)

写个C版本的跑跑看:

分治，动态规划与贪心算法

目录

1 分治算法(Divide and Conquer)

1.1 方法

1.2 示例