动态规划与分治法的思考

如果一个问题具有最优子结构的性质,此外子问题具有重叠性质,那么可以采用自底向上的动态规划的思路进行求解。同时,往往可以用递归的方式自顶向地进行求解,即分治法。如果用分治法去求解这个问题时,能够利用备忘录法进行避免对于子问题的重复计算,那么其计算的效率可以和动态规划的计算效率相比。文章来源:胡小旭 =>动态规划与分治法的思考 Read More

一只青蛙跳出来的分治法、回溯法与动态规划

从2018年7月份开始,基础薄弱的我从0开始刷LeetCode题目。目的性很明确,也很简单——就是为了提高解决问题的思考实践能力,也为了提升自己的核心竞争力。也许,牛人会觉得这并不算什么竞争力。是的,我同意的。但,这是我目前能做的比较基础的事情罢了。迄今(2018年12月28日)为止,已经刷了108道题目。顺序基本上是按照出现的频率(Frequency)来刷的,这个频率在LeetCode上需要订阅后才可以看得到。那么在刷了108道题目后,有那么一些题目会觉得“似曾相识”了,也会有一种触类旁通的感觉了。所以,我觉得应该适当放慢刷题的速度,同时做做总结了。所以,计划了一项视频解说计划,在YouTubeh和B站都建立了《小旭解说算法之路》的频道,欢迎订阅,多多提建议。那么,进入正题。经过了108道题的历练之后,我来说说对于分治法、回溯法和动态规划的理解。我觉得他们三者是一个相互有交集的概念,并不... Read More