在这里,可以思考一下:可以根据第一步的走法把所有走法分为两类:
① 第一类是第一步走了 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)相加。
思考一下:如果反过来,采取自底向上,用迭代的方式进行推导会怎么样了?