利用“记忆化搜索“解斐波那契数
一、题目描述
求第 n 个斐波那契数。
二、 利用"记忆化搜索"解斐波那契数
什么是记忆化搜索？记忆化搜索就是带有备忘录的递归。
我们先来看一下使用递归来解斐波那契数的这个过程，假设求第5个斐波那契数F(5)。
由图可见，要重复计算很多次。
使用记忆化搜索（带有备忘录的递归）来解题时，便不会有重复计算。
如果有一个“备忘录”，我们每次向上返回结果之前，把结果存在“备忘录”一份，下次递归的时候，先看看备忘录，是否有我们需要的值，有的话，直接从备忘录里面取值，就不用再往下递归，便不会有重复计算。
总结：如何实现记忆化搜索？
- 添加一个备忘录 <可变参数，返回值>（对于本题，使用数组即可，可变参数就是数组的下标，代表第几个斐波那契数；返回值就是第几个斐波那契数的值）
- 递归每次返回的时候，将结果放到备忘录里面
- 在每次进入递归的时候，往备忘录里面瞅一瞅
三、解题代码
class Solution {//建一个备忘录，本题使用数组即可int[] memo = new int[31];public int fib(int n) {//初始化数组里面的值，应为下面递归不可能返回的值for(int i = 0; i < 31; i++) {memo[i] = -1;}return dfs(n);}public int dfs(int n) {//每次进⼊递归的时候，先去备忘录里面看看if(memo[n] != -1) {return memo[n];}if(n == 0 || n == 1) {//返回之前，要放在备忘录一份memo[n] = n;return n;}memo[n] = dfs(n-1) + dfs(n-2); //返回之前，要放在备忘录一份return memo[n];}
}四、结果
相关问题：
1、所有的递归（暴搜、深搜），都能改成记忆化搜索吗？
答：不是的，只有在递归过程中，出现了大量完全相同的问题时，才能用记忆化搜索的方式优化。
2、带备忘录的递归、记忆化搜索和动态规划其实都是一回事（本质相同：对解法的优化，把已经计算过的值给存起来）