分治算法分为 “分” 和 “治” 两个部分，所谓的分就是寻找分割点，然后对问题划分成相同的子问题，但是问题的规模变小了，这些步骤其实就是使用递归来完成的。之后就是治的问题，也就是递归里面具体的内容。最后一步就是把所分的结果要合并成为一个完整的结果。 一个例子就是求出逆序数对，这个就是分治法来计算，首席我们分就是中间划分，分别求左右的两边的逆序数对，然后还需要加上横跨中间的逆序数对即可完成。重点就是横跨中间的逆序数对，中间的如果直接暴力枚举就会出现 n 平方的，所以我们首...
HouseRobberIII
The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the “root.” Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that “all houses in ...
Target Sum
You are given a list of non-negative integers, a1, a2, …, an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and - as its new symbol. Find out how many ways to assign symbols to make sum of integer...
QueueReconstructionbyHeight
Suppose you have a random list of people standing in a queue. Each person is described by a pair of integers (h, k), where h is the height of the person and k is the number of people in front of this person who have a height greater than or equal...
Dp经典问题LongestIncreasingSubsequence
Given an unsorted array of integers, find the length of longest increasing subsequence. For example, Given [10, 9, 2, 5, 3, 7, 101, 18], The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more...