今天来搞一个递归算法。
有一只青蛙，一次能跳一级，也能跳两级，问跳n级台阶的时候，有几种方法？
这是一个很简单的递归，它的相应算法似乎也很容易，f(n) = f(n-1)+f(n-2)也就是说，他在第n级台阶跳的方法等于他在n-1级跳的次数加上n-2级跳的次数，于是递推关系式出来了，这个时候只要写出初始项也就是1级和2级的情况，代码也就写出来了
但是这个算法很有问题，运行数一多，它的运行时间会紧跟着往上走，比如说，当30级台阶的时候，它的运行时间为9秒！80级的时候，它就根本运行不出来了。。。。
这是运行时间
所以这边重新引入一种新的算法，记忆化递归。
这名字听得高大上，其实核心就一个，我将每次递归运算得出的结果弄个数组存起来，这样下次直接用就好了，这是它对应的代码：
此时，我的每次上两级函数的值直接用自数组，不需要再重新进行计算，而这个算法对应30级台阶的时间为0毫秒，也就是一瞬间就算出来了，应该说变快了很多很多。
这就是今天介绍的记忆化递归算法，今后凡是遇到需要提高递归效能的，都可以使用记忆化递归算法。每天一个，强身健脑，明天见！
递归常用来解决一些可拆分的，并且拆分到一定程度自然得到解的问题，最经典的就是斐波那契数列（1，1，2，3，5......
今天来搞一个递归算法。 有一只青蛙，一次能跳一级，也能跳两级，问跳n级台阶的时候，有几种方法？ 这是一个很简单的递...
1.字符串为传递参数的递归法2.指针为传递参数的递归法3.记忆化递归法4.动态规划 3.记忆化递归代码
这次针对之前的记忆化递归算法，我们来一个加强版 还是那只青蛙，这次他可以跳的更多，他可以一次跳一级，也可以一次跳两...
递归算法 非递归算法
文章概述 递归算法和尾递归概述递归算法的优化 递归算法 介绍：递归算法是计算机编程领域非常重要的一种算法，采用分而...
递归 注释记忆化搜索 测试用例 背包大小5 耗时 添加记忆化搜索
递归算法是一种直接或者间接调用自身函数或者方法的算法。Java递归算法是基于Java语言实现的递归算法。递归算法的...
递归算法，尾递归算法求阶乘！
递归算法： 迭代算法： 分析 递归算法：规模为n的问题，有n个递归，每个递归又有相应矩阵个数个递归，故T(n)=T...
本文标题：递归算法的记忆化
本文链接：https://www.haomeiwen.com/subject/xgsimktx.html
网友评论