常见算法要点思路小总结
常见算法要点思路小总结
子问题的构思：对于整体的问题的抽象化理解，不要往分解问题的角度去想，而是想排除某个或者某些元素之后问题规模缩小，然后递归调用。同样注意，分治中按照区块进行分组调用，然后合并。
对于初始条件和递归退出条件：分治算法递归的调用是需要退出条件的，而DP算法是需要初始条件去逐层构造
分治算法
-
划分子问题+递归求解子问题+合并子问题——自上而下
-
既然是递归解决子问题，那么递归的要求：递归主体，退出条件都要明确
-
例如寻找在大小为n的数组中找到第i大的数，如果不使用分治算法，需要的时间，使用分治剪枝能够降低到线性时间复杂度。
类似二分查找的思路，以5个数为一组分组，然后对每个组进行排序，因为数量固定，所以只需要常数时间就可以将每组5个数进行排序，最后排好n/5个分组只需要时间，然后筛选出来每组的第三个元素，对这些元素进行递归调用找到整个数组的中位数 ，然后就能像二分查找那样进行剪枝了。
DP算法
-
一般是求解最优问题的
-
关键是找到问题的子问题，并且证明总的大问题取得优化解的时候也是子问题取得优化解的时候；
-
然后写出优化子结构的递归表达式，得到最终的优化解。——自下而上
-
例如找 两个字符串的最长公共字串中，不论是从前还是从后匹配字符，根据首字符是否相同都能把原先问题分割为更小的匹配之后其余字符的子问题，并且用反证法很容易得出在大问题取得最优解的时候也是子问题也是取得最优解的时候，这样就能把大的问题分解为多个子问题进行求解。
其次需要得到递归定义最优解表达式，和分治思路不同，递推需要明确初始条件。
最后得到
-
01背包问题
首先要明确子问题怎么构造：考虑第一个物品是否放置到背包中进行考虑，能放进时放与不放、放不进去时这三种情况将问题分为了子问题，根据反正法很容易得到大的问题取得最优解的时候也是子问题取得最优解的时候。
DP和分治的比较
- DP和分治都是将问题转化成子问题进行求解，但是分治是从问题宏观上进行子问题划分，DP则是划分最小的子问题进行“累计”，到最后得到最优解。
- 分治的递归调用需要一个退出条件，也是“大的问题”是什么情况时可以直接得到结果，只有能确定这个，才能够保证分治的使用
- 分治算法如果划分的子问题有重叠的情况，会导致重复计算，DP解决这个问题，使用空间换时间的策略，将小的问题都存储起来，不必重复计算。
- 两者最重要的——就是找到子问题的表达形式。子问题就是同样功能的小规模问题的解。
者最重要的——就是找到子问题的表达形式。子问题就是同样功能的小规模问题的解。