讨论/算法和数据结构/递归,分治,回溯,动态规划之间的区别和联系是什么/
递归,分治,回溯,动态规划之间的区别和联系是什么

如题

展开讨论

递归:一个函数自己调用自己,或者两个函数互相调用。
分治:分而治之,把一个复杂的问题分成两个或更多的相同或相似的子问题,直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。处理各个小部分的时候可能把部分当作整体去处理,因为部分和整体并没有区别,有点分形的意思。
回溯:回溯的字面意思是撤销之前的决策。回溯一般是用深度优先搜索实现的。在递归调用 dfs 前,会做一步决策并相应地改变全局的状态。在离开当前函数时,会撤销之前在这个函数里做过的决策,也即恢复因这个决策而被改变的全局的状态。
动态规划:直接看看别人的回答吧。什么是动态规划(Dynamic Programming)?动态规划的意义是什么? - Coldwings的回答 - 知乎

区别和联系

展开全部 2 讨论