本文主要是介绍利用“记忆化搜索“解斐波那契数,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
一、题目描述
求第 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、带备忘录的递归、记忆化搜索和动态规划其实都是一回事(本质相同:对解法的优化,把已经计算过的值给存起来)
这篇关于利用“记忆化搜索“解斐波那契数的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!