递归、动规、分治_小船要远航的博客-爱代码爱编程
递归、动态规划、分治都是通过不断分割子问题求解,它们之间的界限不是很明显,但还是有一些区别。
如下:
-
递归
利用函数的递归过程进行求解。
可以利用前进过程求解,也可以利用回退过程求解。
缺点是,递归次数越多,空间复杂度越大,并且可能存在重复子问题的计算。
-
动态规划
将问题分成一个个子问题,从最小的子问题开始求解,利用子问题的解求得最终解。
一般会用Dp数组记录子问题的状态和结果,避免了重复子问题的计算。
-
分治
一般不需要回退和记录过程,当下子问题解决了,最终的问题就解决了。
比如快排,先取一个基准值,通过遍历和比较将数组分成两部分,即两个子问题。之后
重复上述步骤,解决子问题,直到不能再分割出子问题,问题也就解决了。当然快排也
是通过递归进入子问题的。