看动画轻松理解「递归」与「动态规划」(完整版) (2)

先爬 2 个台阶

先爬 2 个台阶

在这里,可以思考一下:可以根据第一步的走法把所有走法分为两类:

① 第一类是第一步走了 1 个台阶

② 第二类是第一步走了 2 个台阶

所以 n 个台阶的走法就等于先走 1 阶后,n-1 个台阶的走法 ,然后加上先走 2 阶后,n-2 个台阶的走法。

用公式表示就是:

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

有了递推公式,递归代码基本上就完成了一半。那么接下来考虑递归终止条件。

当有一个台阶时,我们不需要再继续递归,就只有一种走法。

所以 f(1)=1。

通过用 n = 2,n = 3 这样比较小的数试验一下后发现这个递归终止条件还不足够。

n = 2 时,f(2) = f(1) + f(0)。如果递归终止条件只有一个f(1) = 1,那 f(2) 就无法求解,递归无法结束。
所以除了 f(1) = 1 这一个递归终止条件外,还要有 f(0) = 1,表示走 0 个台阶有一种走法,从思维上以及动图上来看,这显得的有点不符合逻辑。所以为了便于理解,把 f(2) = 2 作为一种终止条件,表示走 2 个台阶,有两种走法,一步走完或者分两步来走。

总结如下:

① 假设只有一个台阶,那么只有一种走法,那就是爬 1 个台阶

② 假设有两个个台阶,那么有两种走法,一步走完或者分两步来走

递归终止条件

递归终止条件

通过递归条件:

1f(1) = 1;
2f(2) = 2;
3f(n) = f(n-1)+f(n-2)

很容易推导出递归代码:

1int f(int n) {
2  if (n == 1) return 1;
3  if (n == 2) return 2;
4  return f(n-1) + f(n-2);
5}

通过上述三个示例,总结一下如何写递归代码:

1.找到如何将大问题分解为小问题的规律

2.通过规律写出递推公式

3.通过递归公式的临界点推敲出终止条件

4.将递推公式和终止条件翻译成代码

什么是动态规划

介绍动态规划之前先介绍一下分治策略(Divide and Conquer)。

分治策略

将原问题分解为若干个规模较小但类似于原问题的子问题(Divide),「递归」的求解这些子问题(Conquer),然后再合并这些子问题的解来建立原问题的解。

因为在求解大问题时,需要递归的求小问题,因此一般用「递归」的方法实现,即自顶向下。

动态规划(Dynamic Programming)

动态规划其实和分治策略是类似的,也是将一个原问题分解为若干个规模较小的子问题,递归的求解这些子问题,然后合并子问题的解得到原问题的解。
区别在于这些子问题会有重叠,一个子问题在求解后,可能会再次求解,于是我们想到将这些子问题的解存储起来,当下次再次求解这个子问题时,直接拿过来就是。
其实就是说,动态规划所解决的问题是分治策略所解决问题的一个子集,只是这个子集更适合用动态规划来解决从而得到更小的运行时间。
即用动态规划能解决的问题分治策略肯定能解决,只是运行时间长了。因此,分治策略一般用来解决子问题相互对立的问题,称为标准分治,而动态规划用来解决子问题重叠的问题。

与「分治策略」「动态规划」概念接近的还有「贪心算法」「回溯算法」,由于篇幅限制,程序员小吴就不在这进行展开,在后续的文章中将分别详细的介绍「贪心算法」、「回溯算法」、「分治算法」,敬请关注:)

将「动态规划」的概念关键点抽离出来描述就是这样的:

1.动态规划法试图只解决每个子问题一次

2.一旦某个给定子问题的解已经算出,则将其记忆化存储,以便下次需要同一个子问题解之时直接查表。

从递归到动态规划

还是以 爬台阶 为例,如果以递归的方式解决的话,那么这种方法的时间复杂度为O(2^n),具体的计算可以查看笔者之前的文章 《冰与火之歌:时间复杂度与空间复杂度》。

相同颜色代表着 爬台阶问题 在递归计算过程中重复计算的部分。

爬台阶的时间复杂度

爬台阶的时间复杂度

通过图片可以发现一个现象,我们是 自顶向下 的进行递归运算,比如:f(n) 是f(n-1)与f(n-2)相加,f(n-1) 是f(n-2)与f(n-3)相加。

思考一下:如果反过来,采取自底向上,用迭代的方式进行推导会怎么样了?

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/wpjpww.html