江苏龙网

  1. 主页 > 生活百科 > >

一文学懂递归和动态规划( 三 )

递归


文章插图
 
但是我们可以看到，空间应该还有优化的余地 。
那仔细想想，其实我们 记笔记的时候需要记录这么多吗 ？需要从幼儿园到小学到初中到高中的笔记都留着吗？
那其实每项的计算 只取决于它前面的两项 ，所以只用保留这两个就好了 。
那我们可以用一个长度为 2 的数组来计算，或者就用 2 个变量 。
更新代码：
class Solution {public int fib(int N) {int a = 0;int b = 1;if(N == 0) {return a;}if(N == 1) {return b;}for(int i = 2; i <= N; i++) {int tmp = a + b;a = b;b = tmp;}return b;}}这样我们就把空间复杂度优化到了 O(1) ，时间复杂度和用数组记录一样都是 O(n) .
这种方法其实就是 动态规划 Dynamic Programming ，写出来的代码非常简单 。
<span style="color:blue">那我们比较一下 Recursion 和 DP：
Recursion是从大到小，层层分解，直到 base case 分解不了了再组合返回上去；
DP
是从小到大，记好笔记，不断进步 。
也就是 Recursion + Cache = DP如何记录这个笔记，如何高效的记笔记，这是 DP 的难点 。
有人说 DP 是拿空间换时间，但我不这么认为，这道题就是一个很好的例证 。在用递归解题时，我们可以看到，空间是 O(n) 在栈上的，但是<span style="display:block;color:blue">用 DP 我们可以把空间优化到 O(1)，DP 可以做到时间空间的双重优化 。</span>
其实呢，斐波那契数列在现实生活中也有很多应用 。
比如在我司以及很多大公司里，每个任务要给分值，1分表示大概需要花1天时间完成，然后分值只有1，2，3，5，8这5种，（如果有大于8分的任务，就需要把它 break down 成8分以内的，以便大家在两周内能完成 。）
披着羊皮的狼<span style="color:blue">那有同学可能会想，这题这么简单，这都 2020 年了，面试还会考么？
答：真的会 。只是不能以这么直白的方式给你了 。
比如很有名的 爬楼梯 问题：
一个 N 阶的楼梯，每次能走一层或者两层，问一共有多少种走法 。
这个题这么想：
站在当前位置，只能是从前一层，或者前两层上来的，所以 f(n) = f(n-1) + f(n-2).
这题是我当年面试时真实被问的，那时我还在写 Python，为了炫技，<span style="color:blue">还用了lambda function:
f = lambda n: 1 if n in (1, 2) else f(n-1) + f(n-2)递归的写法时间复杂度太高，所以又写了一个 for loop 的版本
def fib(n)a, b = 1, 1for i in range(n-1):a, b = b, a+breturn a<span style="color:blue">然后还写了个 caching 的方法:
def cache(f):memo = {}def helper(x):if x not in memo:memo[x] = f(x)return memo[x]return helper@cachedef fibR(n):if n==1 or n==2: return 1return fibR(n-1) + fibR(n-2)<span style="color:blue">还顺便和面试官聊了下 tail recursion:
tail recursion 尾递归：就是递归的这句话是整个方法的最后一句话 。
那这个有什么特别之处呢？
尾递归的特点就是我们可以 很容易的把它转成 iterative 的写法 ，当然有些智能的编译器会自动帮我们做了（不是说显性的转化，而是在运行时按照 iterative 的方式去运行，实际消耗的空间是 O(1)）
那为什么呢？
因为回来的时候不需要 backtrack，递归这里就是最后一步了，不需要再往上一层返值 。
def fib(n, a=0, b=1):if n==0: return aif n==1: return breturn fib(n-1, b, a+b)<span style="color:blue">最终，拿出了我的杀手锏：lambda and reduce
fibRe = lambda n: reduce(lambda x, n: [x[1], x[0]+x[1]], range(n), [0, 1])看到面试官满意的表情后，就开始继续深入的聊了...
所以说，不要以为它简单，同一道题可以用七八种方法来解，分析好每个方法的优缺点，引申到你可以引申的地方，展示自己扎实的基本功，这场面试其实就是你 show off 的机会，这样才能骗过面试官啊～lol
如果你喜欢这篇文章，记得给我点赞留言哦～你们的支持和认可，就是我创作的最大动力，我们下篇文章见！
我是小齐，纽约程序媛，终生学习者，每天晚上 9 点，云自习室里不见不散！更多干货文章见我的 Github: https://github.com/xiaoqi6666...
前言大家好，这里是《齐姐聊算法》系列之递归和 DP 问题 。
递归，是一个非常重要的概念，也是面试中非常喜欢考的 。因为它不但能考察一个程序员的算法功底，还能很好的考察对 时间空间复杂度 的理解和分析 。


推荐阅读


上一篇：12个前端开发必备开发的工具

下一篇：Nginx基本原理和代理模式