内容简介:从2018年7月份开始,基础薄弱的我从0开始刷LeetCode题目。目的性很明确,也很简单——就是为了提高解决问题的思考实践能力,也为了提升自己的核心竞争力。也许,牛人会觉得这并不算什么竞争力。是的,我同意的。但,这是我目前能做的比较基础的事情罢了。迄今(2018年12月28日)为止,已经刷了108道题目。顺序基本上是按照出现的频率(Frequency)来刷的,这个频率在LeetCode上需要订阅后才可以看得到。那么在刷了108道题目后,有那么一些题目会觉得“似曾相识”了,也会有一种触类旁通的感觉了。所以,
从2018年7月份开始,基础薄弱的我从0开始刷LeetCode题目。目的性很明确,也很简单——就是为了提高解决问题的思考实践能力,也为了提升自己的核心竞争力。也许,牛人会觉得这并不算什么竞争力。是的,我同意的。但,这是我目前能做的比较基础的事情罢了。
迄今(2018年12月28日)为止,已经刷了108道题目。顺序基本上是按照出现的频率(Frequency)来刷的,这个频率在LeetCode上需要订阅后才可以看得到。那么在刷了108道题目后,有那么一些题目会觉得“似曾相识”了,也会有一种触类旁通的感觉了。所以,我觉得应该适当放慢刷题的速度,同时做做总结了。
所以,计划了一项视频解说计划,在 YouTubeh 和 B站 都建立了《小旭解说算法之路》的频道,欢迎订阅,多多提建议。
那么, 进入正题 。经过了108道题的历练之后,我来说说对于分治法、回溯法和动态规划的理解。
我觉得他们三者是一个相互有交集的概念,并不是相互完全独立的。至于为什么不是完全独立的,在分别说说这三种方法的解决思路后,我们再终结一下。
分治法(Divide and Conquer)
分治法是解决规模庞大的问题的很好的思路,他通过降低问题的规模,形成若干个规模更小但形式相同的子问题,进行递归求解。在求解过后,将各个子问题的解合并起来,形成原问题的解。
那么它的大致流程主要分成三步:
- 分解(Divide)将大规模的问题分解成若干个规模更小但形式相同的子问题
- 解决(Conquer)如果当前问题的规模足够小,并可以直接解决的话,那么直接解决并返回解。否则,继续进行分解并递归求解分解后的子问题。
- 合并(Merge)将各个子问题合并,最终形成原问题的解。
所以,明确了三步之后,还要明确一件事件——实现方式:递归法。
分治法一般来说会采用递归法来进行实现,当然,利用迭代法(比如for、while)也是可以的。
所以,我们往往看到的递归算法从广义上来说都是分治法。无非就是有些递归算法将问题分解了若干个子问题,然而有些递归算法将问题分解成了一个子问题。那么有些作者会称作前者是分治法,后者是减治法。
其实,这个概念真的非常非常重要。在面对很多问题的时候,都可以用这种思路去思考。那么其中思考的一个非常重要的一点就是递归算法中的边界(跳出)条件的判定。
只要,我们想明白了求解子问题过程中的边界条件,那么问题就会很清晰,并且很容易写出程序来。否则,模糊的边界条件,会导致整个递归算法进入到“死循环”的尴尬地步。
举个例子
青蛙:frog:跳台阶的问题:一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法?
那么如果我们用分治法的思路思考的话,这道题真是非常非常容易理解。
首先,当青蛙在面对第一个台阶时,他只有两种选择——跳一步还是跳两步。如果我们定义f(n)代表青蛙跳跃到n层台阶一共的方法数,那么我们可以将问题进行 分解 两个规模更小,但形式相同的问题:
f(n) = f(n - 1) + f(n - 2)
其中f(n - 1)是青蛙选择跳一步后,剩下的子问题,同理f(n - 2)是青蛙选择跳两步后剩下的子问题。这样,我们就把问题进行了分解。
下面再谈谈如何解决,正如上面谈到的解决步骤,如果规模足够小那么直接返回,否则继续降低规模进行递归求解。这时,就是我们要确定边界条件——即当n = 1 和n = 2时的情况。
在明确了边角条件后,合并就非常的简单,也就是简单的相加即可了。
那么代码写出来是什么样子呢?
#include <iostream> using namespace std; int f(int n) { // 边界条件(解决) if (n < 1) return 0; // 当台阶数目小于1时,那么就返回0种方案数量 if (n == 1) return 1; // 当台阶数目为1时,问题的规模已经足够小,我们可以直接想出他的方案数量—— 即1种:1步 if (n == 2) return 2; // 当台阶数目为2时,他的方案数量为2种,即—— 1步+1步,2步 return f(n - 1) + f(n - 2); // 分解并合并 } int main() { cout<<f(4)<<endl; return 0; }
回溯法(Backtracking)
回溯法,我理解应该也可以叫做深度优先搜索(Depth-First Search)。所以,他是一种搜索算法。
既然谈到搜索,往往这里面会面临选择的情景。以那个青蛙为例,当面对第一个台阶时,他有两个选择。当他选择一种选择后,将“义无反顾”的一条道走下去,每层都会进行一次选择,直到走到地n层位置时。这时,青蛙已经触碰到了边界,并得到了一种方案,之后青蛙会返回到最近的上一次选择时的情景,选择第二种情况继续走下去。以此往复,直到搜索全部的情景。
是的,这非常的抽象。我们来看看用二叉树来描述运动轨迹是怎么样的。我们假设n = 3。
颜色
- 蓝色 代表当前搜索路走过的路径节点
- 白色 代表没有搜索走过的节点
- 红色 代表已经搜索过的节点,不可以再走
左右子树
- 左子树 代表走一步
- 右子树 代表走两步
回溯
如下图中红框标记的位置就是回溯到某一个情况。
如果你理解了下图的运动轨迹,我想差不多对于回溯的搜索过程就基本了解了。所以,你可以找到其他回溯点么?
理解了上图的运动轨迹后,那么,代码是什么样子呢?
#include </iostream><iostream> using namespace std; /** * int count 方案总数 * int target 目标—— 剩余的台阶数 */ void dfs(int& count, int target) { // 边界条件 if (target < = 2) { count += target; // 当剩余一个台阶是即累加一种方案,剩余两个台阶时累加两种方案 return; } // 下面是两个基本点选择一步和选择两步 // 选择一步 dfs(count, target - 1); // 选择两步 dfs(count, target - 2); } int main() { int count = 0; dfs(count, 4); cout<<count<<endl; return 0; }
边界条件
- 剩余一个台阶时,累加一种方案
- 剩余两个台阶时,累加两种方案
再说更重要的选择的两个基本点
- 选择走一步
- 选择走两步
以此进行递归搜索(深度优先搜索DFS),在搜索到边界时进行回溯,以此往复直到搜索到所有情况为止。
动态规划(Dynamic Programming)
动态规划有两个重要的基本性质
最优子结构
如果一个问题的最优解包含了其中子问题的最优解,那么称其具有最优子结构的性质。
什么意思?青蛙在面对n个台阶时的解决方案数是f(n),那么我们知道f(n) = f(n - 1) + f(n - 2)。其中的f(n - 1)与f(n - 2)就是两个子问题的最优解,此时我们可以理解成一个问题的最优解包含了其子问题的最优解,那么这个时候这种问题具有了最优子结构性质。
重叠子问题
这个性质,在我理解是对于上文提到的子问题的补充说明。当解决一个问题时,往往需要依赖于其更小规模的子问题的解,甚至是同时依赖于若干个规模更小的子问题的解,即子问题是被(重复)包含于比其更大的问题中的,所以他是具有重叠子问题的性质。
在这里,多提出一句,这个子问题是在解决当前问题时需要依赖的。即,只有计算了子问题,父问题才可能被求解。这是和贪心算法的重要区别所在。
状态转移方程
dp[i] = dp[i - 1] + dp[i - 2]
- i代表当前问题的规模,即所需要跳过的台阶数。
- dp[i]代表的是跳过i个台阶的方案数量
其实,看到这里我们会发现,根据动态规划和分治法的思路,其解决方案大致是一样的,这一点从其递归关系式和状态转移方程可以看出来。这也是我在前文说到的,分治法与动态规划有交集的一种情况的具体体现。
那么,实现动态规划的方式一共有两种
- 递归法
- 迭代法
其中递归法与分治法的解法是一样的,那么我们用迭代法来实现动态规划的思路。
#include </iostream><iostream> #include <vector> using namespace std; int main() { int n = 4; vector<int> dp(n + 1, 0); dp[1] = 1; dp[2] = 2; for (int i = 3; i < = n; ++i) { dp[i] = dp[i - 1] + dp[i - 2]; } cout<<dp[n]<<endl; return dp[n]; }
总结
通过上面的分析,我们发现其相互相交的共性:
- 递归 动态规划、分治法与回溯法都可以使用递归的方式来实现
- 子问题 分治法、回溯法与动态规划都利用了子问题的解进行决策
那么,就谈到这里面吧。在我理解,上面的三种方式都是面对问题的解决思考的思路,其实这个思路非常的重要。因为思路并不是针对某一个问题,而是某一类问题。在面对很多问题时,如果能够尝试用这几种思路去思考,也许会容易地、顺利地解决问题。
最后,留一个坑,你觉得对于寻求一个整型数组的全排列的问题,能否分别用上述的方式来解决呢?思考一下!
题目:给定无序整型数组nums = [1,2,4,2,-2,10],寻找所有的排列情况。即An1,An2...Ann。
原文链接:胡小旭 => 一只青蛙跳出来的分治法、回溯法与动态规划
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:- 贪心算法和分治算法
- 大整数相乘“分治法”和“循环暴力法”
- 分治思想延伸:数学归纳法、递归、归并排序、MapReduce - 跟黄申老师学数学(python实现)02
- 回溯算法讲解--适用于leetcode绝大多数回溯题目
- 常用算法之回溯法
- leetcode题解(递归和回溯法)
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
算法竞赛入门经典
刘汝佳、陈锋 / 2012-10 / 52.80元
《算法竞赛入门经典:训练指南》是《算法竞赛入门经典》的重要补充,旨在补充原书中没有涉及或者讲解得不够详细的内容,从而构建一个较完整的知识体系,并且用大量有针对性的题目,让抽象复杂的算法和数学具体化、实用化。《算法竞赛入门经典:训练指南》共6章,分别为算法设计基础、数学基础、实用数据结构、几何问题、图论算法与模型和更多算法专题,全书通过近200道例题深入浅出地介绍了上述领域的各个知识点、经典思维方式......一起来看看 《算法竞赛入门经典》 这本书的介绍吧!