记忆化递归讲解

递归

递归有尾递归，中间递归和多重递归，如果递归次数超两次（包括两次）那么递归时就有可能重复递归，使程序变慢

比如利用递归求斐波那契数列的第N项值

#include<iostream>
using namespace std;
int op(int n)
{
	if(n==1||n==2) return 1;
	return op(n-1)+op(n-2);
}
int main()
{
	int n;
	cin>>n;
	cout<<op(n);
	return 0;
}

这是用尾递归求斐波那契数列的第N项

试试输入100结果是什么

没报错，也没输出结果……

这说明程序还在运行……

几分钟后

出来了

显然，这是程序在运行，但是运行太慢，对于一些严格要求速度的题目来说，这是“运行超时”

怎么说呢，来看看斐波那契数列的哈夫曼树图

斐波那契数列的哈夫曼树图

显然，子节点fib(2)被重复执行了5次，加上调用函数时要保留上下文，空间消耗了不少，动态规划是怎样解决斐波那契数列的呢

记忆化方法

将3的值保存，当再次计算到该项时返回该值，于是，这次递归结束，继续往下递归



那么用代码怎么解决呢

创建数组，将其值全部为0

创建一个全局变量的数组，有N个元素，每次将n的值传进数组中，当再一次计算n时直接返回a[n]

#include<iostream>
using namespace std;
int a[101];//假设n不超过100
int main()
{
    int n;
    cin>>n;
    return 0;
}

构建函数框架

#include<iostream>
using namespace std;
int a[101];//假设n不超过100
int fib(int n)
{
    //TODO
}
int main()
{
    int n;
    cin>>n;
    cout<<fib(n);
    return 0;
}

写入代码

#include<iostream>
using namespace std;
int a[101]={0};//这里将数组a全部赋值为0 
int fib(int n)
{
	if(n==1||n==2)
	{
		a[n]=1;
		return 1;
	}
	if(a[n]!=0) return a[n];//如果重复递归直接返回 
	else
	{
		//没有重复将a[n]赋值
		a[n]=fib(n-1)+fib(n-2); 
		return a[n];
	}
}
int main()
{
    int n;
    cin>>n;
    cout<<fib(n);
    return 0;
}

结束语

总结

程序到此完毕，当我们再次输入100时已经可以立刻出来了，一个负数，是因为越界，但是总比等待几分钟后输出来值要好

试试在程序还未加入记忆化算法时输入50是多少，那么现在输入50呢？

下期预告

算法：无，等待ing


备注：


快速幂不写了，算法真的没梗了

I ‘m learning now. Please keep quiet!