【第37天】斐波那契数列与爬楼梯 | 迭代的鼻祖，递推与记忆化

本文已收录于专栏 🌸《Java入门一百例》🌸

序、专栏前言

   本专栏开启，目的在于帮助大家更好的掌握学习Java，特别是一些Java学习者难以在网上找到系统地算法学习资料帮助自身入门算法，同时对于专栏内的内容有任何疑问都可在文章末尾添加我的微信给你进行一对一的讲解。
   但最最主要的还是需要独立思考，对于本专栏的所有内容，能够进行完全掌握，自己完完全全将代码写过一遍，对于算法入门肯定是没有问题的。
   算法的学习肯定不能缺少总结，这里我推荐大家可以到高校算法社区将学过的知识进行打卡，以此来进行巩固以及复习。
  学好算法的唯一途径那一定是题海战略，大量练习的堆积才能练就一身本领。专栏的任何题目我将会从【题目描述】【解题思路】【模板代码】【代码解析】等四板块进行讲解。

一、递推与记忆化

  在算法的学习中，有许多的题目需要我们递推得到答案，这需要我们去发掘出递推式子得到答案。就好比我们在一个有向图上想要到达终点，需要从起点一步步找到终点，所以相邻的点之间一定会有着某种关联，这种关联就是我们的递推式。斐波那契数列和爬楼梯两道题可以说是所有递推入门的经典题目，同时递推思想也可以看作是最简单动态规划思想。当然在递推时，为了减少重复计算，我们还用叫做记忆化的优化方法，可以帮我们节省大量的时间。

二、【例题1】

1、题目描述

写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：

• F(0) = 0, F(1) = 1
• F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
• 斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
  答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

2、解题思路

  核心在于递推式：$$F(N)=F(N-1)+F(N-2)$$

  显然式子含义为每个数为前两个数之和，我们根据式子递推即可。

3、模板代码

超时代码：

class Solution {public int fib(int n) {return f(n);}int f(int x){if(x==1) return 1;if(x==0) return 0;return (f(x-1)+f(x-2))%1000000007;}
}

递归记忆化代码：

class Solution {int[] a=new int[110];public int fib(int n) {Arrays.fill(a,-1);a[0]=0;a[1]=1;dfs(n);return a[n];}int dfs(int x){if(a[x]!=-1) return a[x];return a[x]=(dfs(x-1)+dfs(x-2))%1000000007;}
}

递推代码：

class Solution {public int fib(int n) {if(n==0) return 0;int[] f=new int[n+1];f[0]=0;f[1]=1;for(int i=2;i<=n;++i){f[i]=(f[i-1]+f[i-2])%1000000007;}return f[n];}
}

4、代码解析

  显然，无论是递推还是记忆化代码，我们都需要使用数组记录答案，否则当我们求解 $f(n)$时，本来我们已经计算出了$f(n-1)$和$f(n-2)$，结果又得重新计算一次，从而导致计算量变大超时。可以直接使用数组递推时，其本身就有记忆化功能，如果使用递归来进行 $dp$，则大家最好加上记忆化。

5.原题链接

斐波那契数列

三、【例题1】

1、题目描述

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

2.解题思路

  定义 $f(n)$为走到第 $n$ 阶楼梯有多少种走法，显然第 $n$ 阶只能从第 $n-1$ 或者 $n-2$ 阶走过来，于是我们得到递推式：
$$f(n)=f(n-1)+f(n-2)$$
  (惊喜发现这不是和斐波那契数列一样的吗哈哈哈，那么题目迎刃而解啦，但是注意初始化有略微区别

3、模板代码

递推代码:

class Solution {public int climbStairs(int n) {int[] f=new int[n+1];if(n==1) return 1;f[1]=1;f[2]=2;for(int i=3;i<=n;++i){f[i]=f[i-1]+f[i-2];}return f[n];}
}

递推记忆化代码：

class Solution {int[] f=new int[50];public int climbStairs(int n) {Arrays.fill(f,-1);if(n==1) return 1;f[1]=1;f[2]=2;dfs(n);return f[n];}int dfs(int x){if(f[x]!=-1) return f[x];return f[x]=dfs(x-1)+dfs(x-2);}
}

4、代码解析

注意到爬楼梯和斐波那契初始化不同，递推式相同。

5、原题链接

爬楼梯

三、推荐专栏

🌌《零基础学算法100天》🌌

四、课后习题

序号	题目链接	难度评级
1	使用最小花费爬楼梯	1

👇 学习有疑问？👇