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

本文来源于力扣圈子，作者：胡小旭。（点击查看原文）

从 2018 年 7 月份开始，基础薄弱的我从 0 开始刷力扣。目的性很明确，也很简单 —— 就是为了提高解决问题的思考实践能力，也为了提升自己的核心竞争力。也许，牛人会觉得这并不算什么竞争力。但这是我目前能做的比较基础的事情罢了。

截至 2018 年 12 月 28 日，我已经刷了 108 道题目。顺序基本上是按照面试题目出现的频率（Frequency）来刷的，这个频率在力扣上需要订阅会员后才可以看到。在刷了 108 道题目后，有一些题目会觉得 “似曾相识” ，也会有一种触类旁通的感觉。

进入正题。经过了 108 道题的历练之后，我来说说对于分治法、回溯法和动态规划的理解。

我觉得他们三者是一个相互有交集的概念，并不是相互完全独立的。至于为什么不是完全独立的，在分别阐述这三种方法的解决思路后，我们再总结一下。

分治法（Divide and Conquer）

分治法是解决规模庞大的问题的很好的思路，他通过降低问题的规模，形成若干个规模更小但形式相同的子问题，进行递归求解。在求解过后，将各个子问题的解合并起来，形成原问题的解。

那么它的大致流程主要分成三步：

分解（Divide）将大规模的问题分解成若干个规模更小但形式相同的子问题
解决（Conquer）如果当前问题的规模足够小，并可以直接解决的话，那么直接解决并返回解。否则，继续进行分解并递归求解分解后的子问题。
合并（Merge）将各个子问题合并，最终形成原问题的解。

所以，明确了三步之后，还要明确一件事件——实现方式：递归法。

分治法一般来说会采用递归法来进行实现，当然，利用迭代法（比如 for、while）也是可以的。

所以，我们往往看到的递归算法从广义上来说都是分治法。无非就是有些递归算法将问题分解了若干个子问题，然而有些递归算法将问题分解成了一个子问题。那么有些作者会称作前者是分治法，后者是减治法。

其实，这个概念真的非常非常重要。在面对很多问题的时候，都可以用这种思路去思考。那么其中思考的一个非常重要的一点就是递归算法中的边界（跳出）条件的判定。

只要，我们想明白了求解子问题过程中的边界条件，那么问题就会很清晰，并且很容易写出程序来。否则，模糊的边界条件，会导致整个递归算法进入到“死循环”的尴尬地步。

举个例子

青蛙跳台阶的问题：一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法？

那么如果我们用分治法的思路思考的话，这道题真是非常非常容易理解。

首先，当青蛙在面对第一个台阶时，他只有两种选择——跳一步还是跳两步。如果我们定义 f(n) 代表青蛙跳跃到 n 层台阶一共的方法数，那么我们可以将问题进行分解两个规模更小，但形式相同的问题：

f(n) = f(n - 1) f(n - 2)

其中 f(n-1) 是青蛙选择跳一步后，剩下的子问题，同理 f(n-2) 是青蛙选择跳两步后剩下的子问题。这样，我们就把问题进行了分解。

下面再谈谈如何解决，正如上面谈到的解决步骤，如果规模足够小那么直接返回，否则继续降低规模进行递归求解。这时，就是我们要确定边界条件——即当 n = 1 和 n = 2 时的情况。

在明确了边界条件后，合并就非常的简单，也就是简单的相加即可。

那么代码写出来是什么样子呢？

回溯法（Backtracking）

回溯法，我理解应该也可以叫做深度优先搜索（Depth-First Search）。所以，它是一种搜索算法。

既然谈到搜索，往往这里面会面临选择的情景。以那个青蛙为例，当面对第一个台阶时，他有两个选择。当他选择一种选择后，将“义无反顾”的一条道走下去，每层都会进行一次选择，直到走到地n层位置时。这时，青蛙已经触碰到了边界，并得到了一种方案，之后青蛙会返回到最近的上一次选择时的情景，选择第二种情况继续走下去。以此往复，直到搜索全部的情景。

是的，这非常的抽象。我们来看看用二叉树来描述运动轨迹是怎么样的。我们假设 n = 3。

颜色